제출 #888637

#제출 시각아이디문제언어결과실행 시간메모리
888637Pring별자리 3 (JOI20_constellation3)C++14
100 / 100
349 ms68392 KiB
#include <bits/stdc++.h> using namespace std; #ifdef MIKU #define debug(x...) cout << '[' << #x << "] : ", dout(x) void dout() { cout << endl; } template <typename T, typename ...U> void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); } #else #define debug(...) 39 #endif #define int long long #define fs first #define sc second #define mp make_pair #define FOR(i, j, k) for(int i = j, Z = k; i < k; i++) typedef long long ll; typedef pair<int, int> pii; const int MXN = 200005; int n, m, a[MXN], px[MXN], py[MXN], pc[MXN]; vector<int> v[MXN]; struct SMG { int val[MXN * 4]; void build(int id, int l, int r) { if (l + 1 == r) { val[id] = l; return; } int mid = (l + r) >> 1; build(id * 2 + 1, l, mid); build(id * 2 + 2, mid, r); val[id] = (a[val[id * 2 + 1]] >= a[val[id * 2 + 2]] ? val[id * 2 + 1] : val[id * 2 + 2]); } int query(int id, int l, int r, int _l, int _r) { if (_r <= l || r <= _l) return 0; if (_l <= l && r <= _r) return val[id]; int mid = (l + r) >> 1; int vl = query(id * 2 + 1, l, mid, _l, _r), vr = query(id * 2 + 2, mid, r, _l, _r); return (a[vl] >= a[vr] ? vl : vr); } void DFS(int id, int l, int r) { debug(l, r, val[id]); if (l + 1 == r) return; int mid = (l + r) >> 1; DFS(id * 2 + 1, l, mid); DFS(id * 2 + 2, mid, r); } } smg; struct BIT { int n, val[MXN]; void init(int _n) { n = _n; fill(val + 1, val + n + 1, 0); } void modify(int id, int v) { for (; id <= n; id += (id & -id)) val[id] += v; } int query(int id) { int ans = 0; for (; id > 0; id -= (id & -id)) ans += val[id]; return ans; } } B; namespace CT { int rt, flc = 1; pii ct[MXN], fl[MXN]; // int pos[MXN]; int build(int l, int r) { if (l >= r) return -1; int rt = smg.query(0, 0, n + 1, l, r); ct[rt].fs = build(l, rt); ct[rt].sc = build(rt + 1, r); return rt; } void FLAT(int id) { fl[id].fs = flc++; if (ct[id].fs != -1) FLAT(ct[id].fs); if (ct[id].sc != -1) FLAT(ct[id].sc); fl[id].sc = flc; } void DFS(int id, ll &x) { if (ct[id].fs != -1) DFS(ct[id].fs, x); if (ct[id].sc != -1) DFS(ct[id].sc, x); int ans = 0; for (auto &i : v[id]) { // debug(pc[i], px[i], B.query(fl[px[i]].fs)); int now = pc[i]; now -= B.query(fl[px[i]].fs); ans = max(ans, now); } debug(id, ans); // debug(fl[id].fs, fl[id].sc); x -= ans; B.modify(fl[id].fs, ans); B.modify(fl[id].sc, -ans); // FOR(i, 1, n + 1) cout << B.val[i] << ' '; // cout << endl; } } namespace PUT { set<int> S; vector<pii> op; void DO() { S.insert(0); S.insert(n + 1); FOR(i, 1, n + 1) op.push_back(mp(a[i], i)); FOR(i, 1, m + 1) op.push_back(mp(py[i], -i)); sort(op.begin(), op.end(), greater<pii>()); for (auto &i : op) { int id = abs(i.sc); if (i.sc > 0) S.insert(id); else { auto itr = S.upper_bound(px[id]); auto itl = prev(itr); v[smg.query(0, 0, n + 1, *itl + 1, *itr)].push_back(id); } } } } void miku() { cin >> n; FOR(i, 1, n + 1) cin >> a[i]; cin >> m; FOR(i, 1, m + 1) cin >> px[i] >> py[i] >> pc[i]; smg.build(0, 0, n + 1); CT::rt = smg.query(0, 0, n + 1, 1, n + 1); CT::build(1, n + 1); CT::FLAT(CT::rt); // FOR(i, 1, n + 1) debug(CT::fl[i].fs, CT::fl[i].sc); PUT::DO(); // return; B.init(n); ll ans = 0; CT::DFS(CT::rt, ans); FOR(i, 1, m + 1) ans += pc[i]; // FOR(i, 1, n + 1) ans -= B.query(i); cout << ans << '\n'; } int32_t main() { cin.tie(0) -> sync_with_stdio(false); miku(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

constellation3.cpp: In member function 'void SMG::DFS(long long int, long long int, long long int)':
constellation3.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
constellation3.cpp:45:9: note: in expansion of macro 'debug'
   45 |         debug(l, r, val[id]);
      |         ^~~~~
constellation3.cpp: In function 'void CT::DFS(long long int, ll&)':
constellation3.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
constellation3.cpp:99:9: note: in expansion of macro 'debug'
   99 |         debug(id, ans);
      |         ^~~~~
constellation3.cpp: In function 'void PUT::DO()':
constellation3.cpp:17:37: warning: unused variable 'Z' [-Wunused-variable]
   17 | #define FOR(i, j, k) for(int i = j, Z = k; i < k; i++)
      |                                     ^
constellation3.cpp:116:9: note: in expansion of macro 'FOR'
  116 |         FOR(i, 1, n + 1) op.push_back(mp(a[i], i));
      |         ^~~
constellation3.cpp:17:37: warning: unused variable 'Z' [-Wunused-variable]
   17 | #define FOR(i, j, k) for(int i = j, Z = k; i < k; i++)
      |                                     ^
constellation3.cpp:117:9: note: in expansion of macro 'FOR'
  117 |         FOR(i, 1, m + 1) op.push_back(mp(py[i], -i));
      |         ^~~
constellation3.cpp: In function 'void miku()':
constellation3.cpp:17:37: warning: unused variable 'Z' [-Wunused-variable]
   17 | #define FOR(i, j, k) for(int i = j, Z = k; i < k; i++)
      |                                     ^
constellation3.cpp:133:5: note: in expansion of macro 'FOR'
  133 |     FOR(i, 1, n + 1) cin >> a[i];
      |     ^~~
constellation3.cpp:17:37: warning: unused variable 'Z' [-Wunused-variable]
   17 | #define FOR(i, j, k) for(int i = j, Z = k; i < k; i++)
      |                                     ^
constellation3.cpp:135:5: note: in expansion of macro 'FOR'
  135 |     FOR(i, 1, m + 1) cin >> px[i] >> py[i] >> pc[i];
      |     ^~~
constellation3.cpp:17:37: warning: unused variable 'Z' [-Wunused-variable]
   17 | #define FOR(i, j, k) for(int i = j, Z = k; i < k; i++)
      |                                     ^
constellation3.cpp:146:5: note: in expansion of macro 'FOR'
  146 |     FOR(i, 1, m + 1) ans += pc[i];
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...