fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MOD = 1e9 + 7;
  5.  
  6. int main() {
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.  
  10.     int n;
  11.     cin >> n;
  12.  
  13.     vector<int> p(n);
  14.     vector<int> pos(n);  // pos[val] = where val is located
  15.  
  16.     for (int i = 0; i < n; i++) {
  17.         cin >> p[i];
  18.         pos[p[i]] = i;
  19.     }
  20.  
  21.     // Track min/max positions of first k values (0 to k-1)
  22.     vector<int> mn(n + 1), mx(n + 1);
  23.     int curMn = INT_MAX, curMx = -1;
  24.  
  25.     mn[0] = curMn;
  26.     mx[0] = curMx;
  27.  
  28.     for (int k = 1; k <= n; k++) {
  29.         int loc = pos[k - 1];  // Where is value (k-1)?
  30.         curMn = min(curMn, loc);
  31.         curMx = max(curMx, loc);
  32.         mn[k] = curMn;
  33.         mx[k] = curMx;
  34.     }
  35.  
  36.     // Check if first k values are in same block
  37.     auto ok = [&](int k, int sz) -> bool {
  38.         if (k == 0) return true;
  39.         return (mn[k] / sz) == (mx[k] / sz);
  40.     };
  41.  
  42.     // Find all divisors of n
  43.     vector<int> divs;
  44.     for (int d = 1; d * d <= n; d++) {
  45.         if (n % d == 0) {
  46.             divs.push_back(d);
  47.             if (d * d != n) {
  48.                 divs.push_back(n / d);
  49.             }
  50.         }
  51.     }
  52.     sort(divs.begin(), divs.end());
  53.  
  54.     long long ans = 0;
  55.  
  56.     // For each block size
  57.     for (int sz : divs) {
  58.         // Binary search: how many consecutive values fit in one block?
  59.         int l = 0, r = n;
  60.  
  61.         while (l < r) {
  62.             int m = (l + r + 1) / 2;
  63.  
  64.             if (ok(m, sz)) {
  65.                 l = m;
  66.             } else {
  67.                 r = m - 1;
  68.             }
  69.         }
  70.  
  71.         // MEX is first missing value (capped at block size)
  72.         long long mex = min((long long)sz, (long long)l);
  73.  
  74.         // Add to answer
  75.         long long val = ((long long)sz % MOD) * (mex % MOD);
  76.         ans = (ans + val) % MOD;
  77.     }
  78.  
  79.     cout << ans << "\n";
  80.  
  81.     return 0;
  82. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
29641226
https://ideone.com/Mgvts1
language:
C++14 (gcc 8.3)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!