제출 #1177509

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177509		Zero_OP	Real Mountains (CCO23_day1problem2)	C++20	0 / 25	1 ms	324 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 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;

//struct mint{
//      int v;
//      mint(int v = 0) : v(v) {
//            if(v >= mod) v %= mod;
//      }
//
//      mint& operator += (const mint& o){
//            v += o.v;
//            if(v >= mod) v -= mod;
//            return *this;
//      }
//
//      mint& operator -= (const mint& o){
//            v -= o.v;
//            if(v < 0) v += mod;
//            return *this;
//      }
//
//      mint& operator *= (const mint& o){
//            v = 1LL * v * o.v % mod;
//            return *this;
//      }
//
//      friend bool operator == (const mint& a, const mint& b){ return a.v == b.v; }
//      friend bool operator != (const mint& a, const mint& b){ return a.v != b.v; }
//
//      friend mint operator + (mint a, const mint& b){ return a += b; }
//      friend mint operator - (mint a, const mint& b){ return a -= b; }
//      friend mint operator * (mint a, const mint& b){ return a *= b; }
//
//      friend ostream& operator << (ostream& out, const mint& o){ return out << o.v; }
//};

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];

int 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];
                  if(lo+1 < hi) bad.eb(lo+1, hi-1);
                  lo = hi;
            }
      }

      if(mx_pos + 1 < N){
            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];
                  if(lo+1 < hi) bad.eb(lo+1, hi-1);
                  hi = lo;
            }
      }

      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;
      multiset<int> online;
      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{
                  int l, r; tie(l, r) = bad[id];
                  cnt -= (r - l + 1);
                  for(int j = l; j <= r; ++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){
                  assert(cnt > 0);

                  ll times = nxt_tm - tm;
                  int L = *online.begin();
                  int R = *online.rbegin();
                  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);

                  if(cnt == 1){
                        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);
//                        cout << "haha\n";
//                        cout << dbg(A) << dbg(B) << dbg(tm) << dbg(times) << '\n';
                        ll cur = A + B + tm + 1LL * times * (times - 1) / 2;
                        (ans += (cur % mod)) %= 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);

                  // cout << dbg(qll) << dbg(qlr) << dbg(qrl) << dbg(qrr) << '\n';
                  // cout << dbg(A) << dbg(B) << dbg(tm) << dbg(times) << dbg(cnt) << '\n';

                  ll overtime = 1LL * times * (times - 1) / 2;

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

                  // cout << dbg(case1) << dbg(case2) << '\n';

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

      return 0;
}

/*

5
5 1 1 1 5
132

11
4 1 2 3 6 5 1 4 1 3 2
94

*/

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