제출 #364874

#제출 시각아이디문제언어결과실행 시간메모리
364874Kevin_Zhang_TW청소 (JOI20_sweeping)C++17
10 / 100
11979 ms256052 KiB
#include <bits/extc++.h> #include<bits/stdc++.h> #define pb emplace_back #define AI(i) begin(i), end(i) template<class T> bool chmax(T &val, T nv) { return val < nv ? (val = nv, true) : false; } template<class T> bool chmin(T &val, T nv) { return nv < val ? (val = nv, true) : false; } using namespace std; using ll = long long; #ifdef KEV #define DE(args...) kout("[ " + string(#args) + " ] = ", args) void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; } void kout(){ cerr << endl; } template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); } #else #define DE(...) 0 #define debug(...) 0 #endif // What I should check // 1. overflow // 2. corner cases // Enjoy the problem instead of hurrying to AC // Good luck ! const int qry_t = 1, mody_t = 3, modx_t = 2, ad_t = 4; const int MAX_N = 500010, MAX_Q = 1000010, inf = 1e9 + 7, QK = 20; int m, q, W; vector<pair<int,int>> dust; pair<int,int> trans(int x, int y) { return {x, W - y}; } pair<int,int> trans(pair<int,int> d) { return trans(d.first, d.second); } int cut[MAX_Q], cl; int qt[MAX_Q + MAX_N], qid[MAX_Q + MAX_N], qL[MAX_Q + MAX_N], qx[MAX_Q + MAX_N], qy[MAX_Q + MAX_N]; pair<int,int> ans[MAX_Q + MAX_N]; #define priority_queue __gnu_pbds::priority_queue namespace data { vector<int> belong; //vector<int> lineon[2 << QK]; struct cmpx { bool operator()(int a, int b) const { return dust[a].first > dust[b].first; } }; struct cmpy { bool operator()(int a, int b) const { return dust[a].second < dust[b].second; } }; // small comes out //priority_queue<int, vector<int>, cmpx> linex[2 << QK]; priority_queue<int, cmpx> linex[2 << QK]; // big comes out //priority_queue<int, vector<int>, cmpy> liney[2 << QK]; priority_queue<int, cmpy> liney[2 << QK]; priority_queue<int, cmpx>::point_iterator px[MAX_Q + MAX_N]; priority_queue<int, cmpy>::point_iterator py[MAX_Q + MAX_N]; pair<int,int> treeLR[2 << QK]; bool ok[MAX_N + MAX_Q]; vector<int> inside; int cnt[2 << QK]; int create_dust(int x, int y) { belong.pb(0); dust.pb(x, y); return dust.size() - 1; } void putin(int sid, int tid) { belong[sid] = tid; px[sid] = linex[tid].push(sid); py[sid] = liney[tid].push(sid); } void dfsclear(int L = 0, int R = cl - 1, int i = 1) { if (cnt[i] == 0) return; treeLR[i] = treeLR[0], cnt[i] = 0; // priority_queue<int, vector<int>, cmpx>().swap(linex[i]); // priority_queue<int, vector<int>, cmpy>().swap(liney[i]); priority_queue<int, cmpx>().swap(linex[i]); priority_queue<int, cmpy>().swap(liney[i]); if (L == R) return; int M = L + R >> 1; dfsclear(L, M, i<<1), dfsclear(M+1, R, i<<1|1); } void init_tree() { dfsclear(); for (int i : inside) ok[i] = false, belong[i] = 0; inside.clear(); } void insertseg(int id, int L = 0, int R = cl - 1, int i = 1) { const auto &[l, r] = dust[id]; int M = L + R >> 1, mid = cut[ M ]; ++cnt[i]; DE(l, r, mid); if (l <= mid && r >= mid) { putin(id, i); return; } if (L == R) { belong[id] = 0; return; } if (l < mid) insertseg(id, L, M, i << 1); else insertseg(id, M+1, R, i << 1|1); } void addseg(int id) { inside.pb(id); ok[id] = true; insertseg(id); DE(dust[id].first, dust[id].second); } bool chmnmx(pair<int,int> &loc, int L, int R) { return chmax(loc.first, L) || chmin(loc.second, R); } bool chmnmx(pair<int,int> &loc, pair<int,int> p) { return chmnmx(loc, p.first, p.second); } pair<int,int> qry(int id) { int mas = belong[id]; if (mas) { chmnmx(dust[id], treeLR[ mas ].first, treeLR[ mas ].second); } //DE(id, belong[id], dust[id].first, dust[id].second); return dust[id]; } void init_all() { DE("cut"); debug(cut, cut + cl); fill(treeLR, treeLR + (MAX_Q << 1), make_pair(0, inf)); } void modiseg(int nL, int nR, int L = 0, int R = cl - 1, int i = 1) { int M = L + R >> 1, mid = cut[ M ]; int P = nL == 0 ? nR : nL; DE(nL, nR, P, cut[M], i); if ((nL == 0 && P >= mid) || (nL != 0 && P <= mid)) chmnmx(treeLR[i], nL, nR); ++cnt[i]; auto kill = [&](int id) { linex[i].erase(px[id]); liney[i].erase(py[id]); }; if (nL >= mid || nR <= mid) { DE("Modi ", nL, nR, P, cut[M], i); // nL == 0 means that now is R bound // need to take max y vector<int> reinsert; if (P == nL) { auto &pq = liney[i]; while (pq.size()) { if (dust[ pq.top() ].second < P) break; int id = pq.top(); if (belong[id] != i) { pq.pop(); continue; } if (chmnmx(dust[id], treeLR[i])) { liney[i].modify(py[id], id); linex[i].modify(px[id], id); continue; } assert(dust[id].first <= P && dust[id].second >= P); chmax(dust[id].first, P); kill(id); reinsert.pb(id); } } else { auto &pq = linex[i]; while (pq.size()) { if (dust[ pq.top() ].first > P) break; int id = pq.top(); if (belong[id] != i) { pq.pop(); continue; } if (chmnmx(dust[id], treeLR[i])) { liney[i].modify(py[id], id); linex[i].modify(px[id], id); continue; } if (dust[id].first > P || dust[id].second < P) { pq.push(id); continue; } assert(dust[id].first <= P && dust[id].second >= P); kill(id); chmin(dust[id].second, P); reinsert.pb(id); } } for (int id : reinsert) insertseg(id, L, R, i); } if (L == R || P == mid) return; if (P < mid) modiseg(nL, nR, L, M, i<<1); else modiseg(nL, nR, M+1,R,i<<1|1); } void updateans(int qd) { int id = qid[qd]; if (ok[id]) { ans[qd] = qry(id); } } } void mody(int L) { DE(0, L); data::modiseg(0, L); // for (auto &[x, y] : dust) // if (x <= L) chmin(y, L); } void modx(int L) { DE(L, inf); data::modiseg(L, inf); // for (auto &[x, y] : dust) // if (y >= L) chmax(x, L); } void cdqsolve(int L, int R) { // // m is dust cnt in the beggining // if (R < m) return; // // // //// //// // for (int i = 0;i < m;++i) // qid[i] = data::create_dust(qx[i], qy[i]); // for (int i = 0;i < m;++i) // data::addseg(qid[i]); // // for (int i = m;i <= R;++i) { // if (qt[i] == qry_t) // data::updateans(i); // if (qt[i] == mody_t) // mody(qL[i]); // if (qt[i] == modx_t) // modx(qL[i]); // } // // //// //// //// //// // return; if (L == R) { if (qt[L] == ad_t) qid[L] = data::create_dust(qx[L], qy[L]); return; } int M = L + R >> 1; cdqsolve(L, M); DE(L, M, R); if (true) { data::init_tree(); for (int i = L;i <= M;++i) if (qt[i] == ad_t) { data::addseg(qid[i]); } for (int i = M+1;i <= R;++i) { if (qt[i] == qry_t) data::updateans(i); if (qt[i] == mody_t) mody(qL[i]); if (qt[i] == modx_t) modx(qL[i]); } for (int i = L;i <= M;++i) if (qt[i] == ad_t) dust[ qid[i] ] = data::qry(qid[i]); } cdqsolve(M+1, R); } int32_t main() { ios_base::sync_with_stdio(0), cin.tie(0); cin >> W >> m >> q; for (int i = 0;i < m;++i) { qt[i] = ad_t; cin >> qx[i] >> qy[i]; tie(qx[i], qy[i]) = trans(qx[i], qy[i]); qid[i] = i; } for (int i = m, t;i < m + q;++i) { cin >> qt[i]; t = qt[i]; // qry dust id if (t == qry_t) { cin >> qid[i]; --qid[i]; } if (t == mody_t || t == modx_t){ cin >> qL[i]; if (t == modx_t) qL[i] = W - qL[i]; cut[cl++] = qL[i]; } // add dust if (t == 4) { cin >> qx[i] >> qy[i]; tie(qx[i], qy[i]) = trans(qx[i], qy[i]); } } sort(cut, cut + cl); cl = unique(cut, cut + cl) - cut; data::init_all(); cdqsolve(0, m + q - 1); for (int i = m;i < m + q;++i) { if (qt[i] == qry_t) { ans[i] = trans(ans[i]); auto [x, y] = ans[i]; cout << x << ' ' << y << '\n'; } } }

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

sweeping.cpp: In function 'void data::dfsclear(int, int, int)':
sweeping.cpp:86:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |   int M = L + R >> 1;
      |           ~~^~~
sweeping.cpp: In function 'void data::insertseg(int, int, int, int)':
sweeping.cpp:99:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |   int M = L + R >> 1, mid = cut[ M ];
      |           ~~^~~
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:102:3: note: in expansion of macro 'DE'
  102 |   DE(l, r, mid);
      |   ^~
sweeping.cpp: In function 'void data::addseg(int)':
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:122:3: note: in expansion of macro 'DE'
  122 |   DE(dust[id].first, dust[id].second);
      |   ^~
sweeping.cpp: In function 'void data::init_all()':
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:142:3: note: in expansion of macro 'DE'
  142 |   DE("cut");
      |   ^~
sweeping.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define debug(...) 0
      |                    ^
sweeping.cpp:143:3: note: in expansion of macro 'debug'
  143 |   debug(cut, cut + cl);
      |   ^~~~~
sweeping.cpp: In function 'void data::modiseg(int, int, int, int, int)':
sweeping.cpp:148:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  148 |   int M = L + R >> 1, mid = cut[ M ];
      |           ~~^~~
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:151:3: note: in expansion of macro 'DE'
  151 |   DE(nL, nR, P, cut[M], i);
      |   ^~
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:167:3: note: in expansion of macro 'DE'
  167 |   DE("Modi ", nL, nR, P, cut[M], i);
      |   ^~
sweeping.cpp: In function 'void mody(int)':
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:247:2: note: in expansion of macro 'DE'
  247 |  DE(0, L);
      |  ^~
sweeping.cpp: In function 'void modx(int)':
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:253:2: note: in expansion of macro 'DE'
  253 |  DE(L, inf);
      |  ^~
sweeping.cpp: In function 'void cdqsolve(int, int)':
sweeping.cpp:295:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  295 |  int M = L + R >> 1;
      |          ~~^~~
sweeping.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
sweeping.cpp:299:2: note: in expansion of macro 'DE'
  299 |  DE(L, M, R);
      |  ^~
#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...