Submission #1113080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113080		duckindog	Real Mountains (CCO23_day1problem2)	C++17	25 / 25	2900 ms	198472 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 1'000'000 + 10,
          M = 1'000'003,
          MAX = 1'000'000'001;
int n;
int h[N];

int prefMax[N], suffMax[N];
int goalH[N];

int f[N << 2];
void build(int s, int l, int r) { 
  if (l == r) { 
    f[s] = h[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(s << 1, l, mid); build(s << 1 | 1, mid + 1, r);
  f[s] = min(f[s << 1], f[s << 1 | 1]);
}
void update(int s, int l, int r, int p, int x) { 
  if (p < l || p > r) return;
  if (l == r) { 
    f[s] = x;
    return;
  }
  int mid = (l + r) >> 1;
  update(s << 1, l, mid, p, x); update(s << 1 | 1, mid + 1, r, p, x);
  f[s] = min(f[s << 1], f[s << 1 | 1]);
}
int query(int s, int l, int r, int u, int v) { 
  if (v < l || u > r) return MAX;
  if (u <= l && r <= v) return f[s];
  int mid = (l + r) >> 1;
  return min(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v));
}

set<int> s[N];
vector<int> del[N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> h[i];

  build(1, 1, n);
  
  vector<int> allValue(h + 1, h + n + 1);
  sort(allValue.begin(), allValue.end());
  allValue.erase(unique(allValue.begin(), allValue.end()), allValue.end());

  for (int i = 1; i <= n; ++i) 
    h[i] = lower_bound(allValue.begin(), allValue.end(), h[i]) - allValue.begin();

  for (int i = 1; i <= n; ++i) prefMax[i] = max(prefMax[i - 1], h[i]);
  for (int i = n; i >= 1; --i) suffMax[i] = max(suffMax[i + 1], h[i]);

  for (int i = 1; i <= n; ++i) goalH[i] = min(prefMax[i], suffMax[i]);
  
  for (int i = 1; i <= n; ++i) { 
    s[h[i]].insert(i);
    del[goalH[i]].push_back(i);
  }

  auto sum = [&](int l, int r) { 
    return (1ll * (r + l) * (r - l + 1) / 2) % M;
  };

  auto add = [&](auto& x, const auto& y) { 
    x += y;
    if (x >= M) x -= M;
  };

  int answer = 0;
  set<int> vt;
  for (int it = 0; it < (int)allValue.size() - 1; ++it) { 
    int height = allValue[it], nxtHeight = allValue[it + 1];
    
    for (const auto& i : s[it]) { 
      vt.insert(i);
      update(1, 1, n, i, MAX);
    }
    for (const auto& i : del[it]) vt.erase(i);

    if (!vt.size()) continue;
    
    int cnt = nxtHeight - height;
    if (vt.size() == 1) { 
      int i = *vt.begin();
      add(answer, 1ll * cnt * (query(1, 1, n, 1, i) + query(1, 1, n, i, n)) % M);
      add(answer, sum(height, nxtHeight - 1));
    } else { 
      int l = *vt.begin(), r = *vt.rbegin();

      long long addLFirst = 1ll * query(1, 1, n, 1, l) + query(1, 1, n, l, n) +
                            query(1, 1, n, r, n);
      long long addRFirst = 1ll * query(1, 1, n, 1, r) + query(1, 1, n, r, n) +
                            query(1, 1, n, 1, l);
      
      add(answer, min(addLFirst, addRFirst) % M * cnt % M);
      add(answer, sum(height, nxtHeight - 1));
      add(answer, sum(height, nxtHeight - 1));
      add(answer, sum(height + 1, nxtHeight));

      int total = 0;
      add(total, sum(height, nxtHeight - 1));
      add(total, sum(height + 1, nxtHeight));
      add(total, sum(height + 1, nxtHeight));
      
      add(answer, 1ll * (vt.size() - 2) * total % M);
    }
  }

  cout << answer << "\n";
}

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 3 / 3
• Subtask 4: 3 / 3
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 4 / 4