Submission #968037

#TimeUsernameProblemLanguageResultExecution timeMemory
968037PringReal Mountains (CCO23_day1problem2)C++17
10 / 25
825 ms84896 KiB
#include <bits/stdc++.h> using namespace std; #ifdef MIKU string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m"; #define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x) void dout() { cout << dbrs << endl; } template <typename T, typename ...U> void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); } #else #define debug(...) 39 #endif #define fs first #define sc second #define mp make_pair #define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++) using ll = long long; typedef pair<int, int> pii; typedef array<int, 3> p3i; const int MXN = 1000005, mod = 1000003, INF = 2e9; int n, a[MXN]; int tg[MXN], cnt; vector<p3i> op; ll tri(int l, int r) { return ((l + r - 1) * (r - l) / 2) % mod; } pii operator+(pii a, pii b) { return mp(min(a.fs, b.fs), max(a.sc, b.sc)); } struct SMG1 { pii val[MXN * 2]; void init(int _n) { fill(val, val + 2 * n, mp(INF, -INF)); } void modify(int p, pii v) { val[p += n] = v; for (p >>= 1; p; p >>= 1) val[p] = val[p << 1] + val[p << 1 | 1]; } pii query(int l, int r) { pii ans = mp(INF, -INF); for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l & 1) ans = ans + val[l++]; if (r & 1) ans = ans + val[--r]; } return ans; } } S; struct SMG2 { int val[MXN * 2]; void init(int n, int *a) { copy(a, a + n, val + n); for (int i = n - 1; i; i--) val[i] = min(val[i << 1], val[i << 1 | 1]); } void modify(int p, int v) { val[p += n] = v; for (p >>= 1; p; p >>= 1) val[p] = min(val[p << 1], val[p << 1 | 1]); } int query(int l, int r) { int ans = INF; for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l & 1) ans = min(ans, val[l++]); if (r & 1) ans = min(ans, val[--r]); } return ans; } } smg; void GET_TG() { int l = 0, r = n - 1; int now = 0, big = *max_element(a, a + n); while (a[l] < big) { now = max(now, a[l]); tg[l] = now; l++; } now = 0; while (a[r] < big) { now = max(now, a[r]); tg[r] = now; r--; } FOR(i, l, r + 1) tg[i] = big; } int calc(int t0, int t1) { if (cnt == 0) return 0; if (t0 == t1) return 0; debug("CALC", t0, t1, cnt); if (cnt == 1) { int x = S.query(0, n).fs; int A = smg.query(0, x), B = smg.query(x + 1, n); return ((t1 - t0) * (A + B) + tri(t0, t1)) % mod; } auto [l, r] = S.query(0, n); int A = smg.query(0, l), B = smg.query(l + 1, n); int C = smg.query(0, r), D = smg.query(r + 1, n); debug(A, B, C, D); return ((t1 - t0) * (A + D + min(B, C) + 2 * cnt - 3) % mod + (3 * cnt - 3) * tri(t0, t1) % mod) % mod; } void miku() { cin >> n; FOR(i, 0, n) cin >> a[i]; GET_TG(); // FOR(i, 0, n) cout << a[i] << ' '; // cout << endl; // FOR(i, 0, n) cout << tg[i] << ' '; // cout << endl; S.init(n); smg.init(n, a); FOR(i, 0, n) { op.push_back(p3i{a[i], 1, i}); op.push_back(p3i{a[i], 2, i}); op.push_back(p3i{tg[i], 3, i}); } sort(op.begin(), op.end()); int time = 0; ll ans = 0; for (auto [t, tp, id] : op) { ans = (ans + calc(time, t)) % mod; time = t; debug(t); if (tp == 1) { debug("KICK", id); smg.modify(id, INF); } else if (tp == 2) { debug("PUSH", id); S.modify(id, mp(id, id)); cnt++; } else { debug("POP", id); S.modify(id, mp(INF, -INF)); cnt--; } debug(ans); } cout << ans << '\n'; } int32_t main() { cin.tie(0) -> sync_with_stdio(false); cin.exceptions(cin.failbit); miku(); return 0; }

Compilation message (stderr)

Main.cpp: In function 'int calc(int, int)':
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:94:5: note: in expansion of macro 'debug'
   94 |     debug("CALC", t0, t1, cnt);
      |     ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:103:5: note: in expansion of macro 'debug'
  103 |     debug(A, B, C, D);
      |     ^~~~~
Main.cpp: In function 'void miku()':
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:128:9: note: in expansion of macro 'debug'
  128 |         debug(t);
      |         ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:130:13: note: in expansion of macro 'debug'
  130 |             debug("KICK", id);
      |             ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:133:13: note: in expansion of macro 'debug'
  133 |             debug("PUSH", id);
      |             ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:137:13: note: in expansion of macro 'debug'
  137 |             debug("POP", id);
      |             ^~~~~
Main.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
Main.cpp:141:9: note: in expansion of macro 'debug'
  141 |         debug(ans);
      |         ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...