Submission #1177526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177526		Zero_OP	Real Mountains (CCO23_day1problem2)	C++20	25 / 25	2395 ms	172652 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i = (l); i < (r); ++i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define int long long

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define compact(v) v.erase(unique(all(v)), end(v))

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ld = long double;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vc = vector<char>;
using vd = vector<db>;

using vpi = vector<pi>;
using vpl = vector<pl>;

const int mod = 1e6 + 3;
const int MAX = 1e6 + 5;
const int inf = 1e9 + 9;

struct MinSegmentTree{
      vpi st;
      int n;
      MinSegmentTree(int n) : n(n), st(n << 2) {
            build(1, 0, n-1);
      }

      void build(int id, int l, int r){
            if(l == r){
                  st[id] = mp(inf, l);
            } else{
                  int mid = l + r >> 1;
                  build(id << 1, l, mid);
                  build(id << 1 | 1, mid + 1, r);
                  st[id] = min(st[id << 1], st[id << 1 | 1]);
            }
      }

      void update(int id, int l, int r, int pos, int val){
            if(l == r) st[id].ff = val;
            else{
                  int mid = l + r >> 1;
                  if(pos <= mid) update(id << 1, l, mid, pos, val);
                  else update(id << 1 | 1, mid + 1, r, pos, val);
                  st[id] = min(st[id << 1], st[id << 1 | 1]);
            }
      }

      int query(int id, int l, int r, int u, int v){
            if(v < l || u > r) return inf;
            if(u <= l && r <= v) return st[id].ff;
            int mid = l + r >> 1;
            return min(query(id << 1, l, mid, u, v), query(id << 1 | 1, mid + 1, r, u, v));
      }

      void refine(int threshold){
            while(st[1].ff <= threshold){
                  update(1, 0, n-1, st[1].ss, inf);
            }
      }

      void update(int pos, int val){
            update(1, 0, n-1, pos, val);
      }
};

int N, H[MAX], f[MAX], fl[MAX], fr[MAX];

signed main(){
      // ios_base::sync_with_stdio(0);
#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif //LOCAL

      cin >> N;
      for(int i = 0; i < N; ++i) {
            cin >> H[i];
      }

      int mx_pos = max_element(H, H + N) - H;
      stack<int> st;

      vector<pair<int, int>> bad;

      if(mx_pos > 0){
            f[mx_pos] = H[mx_pos];
            st.push(mx_pos);
            for(int i = mx_pos - 1; i >= 0; --i){
                  while(!st.empty() && H[st.top()] < H[i]) st.pop();
                  st.push(i);
            }

            int lo = st.top(); st.pop();
            while(!st.empty()){
                  int hi = st.top(); st.pop();
                  for(int i = lo; i < hi; ++i) f[i] = H[lo];
                  // for(int i = 0; i < N; ++i) cout << f[i] << ' '; cout << '\n';
                  if(lo+1 < hi) bad.eb(lo+1, hi-1);
                  lo = hi;
            }
      }

      if(mx_pos + 1 < N){
            f[mx_pos] = H[mx_pos];
            assert(st.empty());
            st.push(mx_pos);
            for(int i = mx_pos + 1; i < N; ++i){
                  while(!st.empty() && H[st.top()] < H[i]) st.pop();
                  st.push(i);
            }

            int hi = st.top(); st.pop();
            while(!st.empty()){
                  int lo = st.top(); st.pop();
                  for(int i = lo + 1; i <= hi; ++i) f[i] = H[hi];
                  // for(int i = 0; i < N; ++i) cout << f[i] << ' '; cout << '\n';
                  if(lo+1 < hi) bad.eb(lo+1, hi-1);
                  hi = lo;
            }
      }

      // for(int i = 0; i < N; ++i) cout << f[i] << ' '; cout << '\n';
      // return 0;

      MinSegmentTree tr(N);
      for(int i = 0; i < N; ++i) {
//            cout << f[i] << ' ';
            tr.update(i, H[i]);
      }
//      cout << '\n';

      vector<tuple<int, int, int>> events;
      set<int> online;
      for(int i = 0; i < N; ++i) events.eb(H[i], 0, i); //dummy
      for(int i = 0; i < sz(bad); ++i){
            int l, r;
            tie(l, r) = bad[i];
            for(int j = l; j <= r; ++j){
                  events.eb(H[j], -1, j);
            }
            events.eb(min(H[l-1], H[r+1]), +1, i);
//            cout << dbg(l) << dbg(r) << dbg(H[l-1]) << dbg(H[r+1]) << '\n';
      }

      sort(all(events));

      int cnt = 0;
      ll ans = 0;
      for(int i = 0; i < sz(events); ++i){
            int tm, type, id;
            tie(tm, type, id) = events[i];

            tr.refine(tm);

            if(type == -1){
                  ++cnt;
                  online.insert(id);
            } else if(type == +1){
                  int l, r; tie(l, r) = bad[id];
                  cnt -= (r - l + 1);
                  for(int j = l; j <= r; ++j) {
                        assert(online.count(j));
                        online.erase(j);
                  }
            }

            if(i == sz(events) - 1) continue;
            int nxt_tm, nxt_type, nxt_id;
            tie(nxt_tm, nxt_type, nxt_id) = events[i+1];

            if(tm != nxt_tm && cnt > 0){

                  ll times = nxt_tm - tm;
                  int L = *online.begin();
                  int R = *online.rbegin();
                  ll overtime = (1LL * times * (times - 1) / 2) % mod;

                  if(cnt == 1){
                        assert(L == R);
                        int A = tr.query(1, 0, N-1, 0, L-1);
                        int B = tr.query(1, 0, N-1, R+1, N-1);
                        if(A > B) swap(A, B);
                        ll cur = (((A + B) * times) % mod + ((tm * times) % mod) + overtime) % mod;
                        (ans += cur);
                        ans %= mod;
                        continue;
                  }

                  ll qll = tr.query(1, 0, N-1, 0, L-1);
                  ll qlr = tr.query(1, 0, N-1, L+1, N-1);
                  ll qrl = tr.query(1, 0, N-1, 0, R-1);
                  ll qrr = tr.query(1, 0, N-1, R+1, N-1);

                  ll case1 = (qll + qlr + qrr); //constructing the left end point first
                  ll case2 = (qrl + qrr + qll); //constructing the right end point first

                  ll two_endpoints = (((min(case1, case2) % mod * times) % mod) + ((3 * tm * times % mod) + (times + overtime * 3) % mod)) % mod;
                  ll middle_part = ((((3 * tm * times % mod) + 2 * times) % mod) + overtime * 3) % mod;
                  two_endpoints %= mod;
                  middle_part %= mod;
                  middle_part = 1LL * middle_part * (cnt - 2) % mod;
                  middle_part %= mod;
                  (ans += (two_endpoints + middle_part) % mod);
                  ans %= mod;
            }
      }
      cout << ans << '\n';

      return 0;
}

• 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