제출 #413995

#제출 시각아이디문제언어결과실행 시간메모리
413995_fractal자리 배치 (IOI18_seats)C++14
70 / 100
4045 ms181520 KiB
#include "seats.h" #include <iostream> #include <climits> using namespace std; #define pb push_back #define S second #define F first typedef pair<int, int> pii; const int N = 2e6 + 200; const int inf = (1 << 30); int S, ans = 0; int H, W; pair<int, int> pos[N], act[N]; int rx[N], lx[N], ry[N], ly[N], val[N]; struct tree_line { int t[N << 2], p[N << 2]; int cnt[N << 2]; void push(int v, int tl, int tr) { if (p[v] != 0) { if (tl != tr) { p[v * 2] += p[v]; p[v * 2 + 1] += p[v]; } t[v] += p[v]; p[v] = 0; } } void build(int v = 1, int tl = 1, int tr = S) { cnt[v] = tr - tl + 1; if (tl == tr) return; int tm = tl + tr >> 1; build(v * 2, tl, tm); build(v * 2 + 1, tm + 1, tr); } void out(int v = 1, int tl = 1, int tr = S) { push(v, tl, tr); if (tl == tr) { cerr << t[v] << " "; return; } int tm = tl + tr >> 1; out(v * 2, tl, tm); out(v * 2 + 1, tm + 1, tr); t[v] = min(t[v * 2], t[v * 2 + 1]); cnt[v] = 0; if (t[v] == t[v * 2]) cnt[v] += cnt[v * 2]; if (t[v] == t[v * 2 + 1]) cnt[v] += cnt[v * 2 + 1]; } void upd(int l, int r, int val, int v = 1, int tl = 1, int tr = S) { push(v, tl, tr); if (l <= tl && tr <= r) { p[v] += val; push(v, tl, tr); return; } if (r < tl || tr < l) return; int tm = tl + tr >> 1; upd(l, r, val, v * 2, tl, tm); upd(l, r, val, v * 2 + 1, tm + 1, tr); t[v] = min(t[v * 2], t[v * 2 + 1]); cnt[v] = 0; if (t[v] == t[v * 2]) cnt[v] += cnt[v * 2]; if (t[v] == t[v * 2 + 1]) cnt[v] += cnt[v * 2 + 1]; } int get() { push(1, 1, S); return cnt[1]; } } tt; struct tree { pii t[N << 2]; int SZ; void upd(int v, int val) { v = v + SZ - 1; t[v] = {val, val}; if (val == inf) t[v].F *= -1; v >>= 1; while (v) { t[v].F = max(t[v * 2].F, t[v * 2 + 1].F); t[v].S = min(t[v * 2].S, t[v * 2 + 1].S); v >>= 1; } } pii get(int l, int r) { l = l + SZ - 1; r = r + SZ - 1; pii ans = {-inf, +inf}; while (true) { if (l % 2 == 1) { ans.F = max(ans.F, t[l].F); ans.S = min(ans.S, t[l].S); } if (r % 2 == 0) { ans.F = max(ans.F, t[r].F); ans.S = min(ans.S, t[r].S); } if (l == r) break; l = (l + 1) >> 1; r = (r - 1) >> 1; } return ans; } } tx, ty; void give_initial_chart(int _H, int _W, vector<int> R, vector<int> C) { H = _H, W = _W; S = H * W; for (int i = 0; i < H * W; ++i) { pos[i + 1] = {R[i] + 1, C[i] + 1}; val[C[i] + 1] = i + 1; } if (H == 1) { tt.build(); val[0] = S + 1; val[S + 1] = S + 1; for (int i = 1; i <= S + 1; ++i) { tt.upd(min(val[i - 1], val[i]), max(val[i - 1], val[i]) - 1, 1); } return; } if (H <= 1000 && W <= 1000) { tx.SZ = 1; while (tx.SZ < S) tx.SZ <<= 1; ty.SZ = tx.SZ; for (int i = 1; i <= tx.SZ; ++i) { if (i > S) { tx.upd(i, +inf); ty.upd(i, +inf); } else { tx.upd(i, pos[i].F); ty.upd(i, pos[i].S); } } return; } rx[0] = -inf, lx[0] = +inf; ry[0] = -inf, ly[0] = +inf; for (int i = 1; i <= S; ++i) { rx[i] = max(rx[i - 1], pos[i].F); lx[i] = min(lx[i - 1], pos[i].F); ry[i] = max(ry[i - 1], pos[i].S); ly[i] = min(ly[i - 1], pos[i].S); if ((rx[i] - lx[i] + 1) * (ry[i] - ly[i] + 1) == i) ans++; } return; } int get(int pos) { pair<int, int> a = tx.get(1, pos); pair<int, int> b = ty.get(1, pos); return (a.F - a.S + 1) * 1LL * (b.F - b.S + 1); } void del(int pos, bool c = 0) { if (!c) tt.upd(min(val[pos - 1], val[pos]), max(val[pos - 1], val[pos]) - 1, -1); pos++; tt.upd(min(val[pos - 1], val[pos]), max(val[pos - 1], val[pos]) - 1, -1); } void add(int pos, bool c = 0) { if (!c) tt.upd(min(val[pos - 1], val[pos]), max(val[pos - 1], val[pos]) - 1, +1); pos++; tt.upd(min(val[pos - 1], val[pos]), max(val[pos - 1], val[pos]) - 1, +1); } int swap_seats(int a, int b) { ++a, ++b; if (a > b) swap(a, b); if (H == 1) { if (pos[a].S > pos[b].S) swap(a, b); del(pos[a].S); if (pos[a].S + 1 < pos[b].S) del(pos[b].S); else del(pos[b].S, 1); } swap(pos[a], pos[b]); val[pos[a].S] = a; val[pos[b].S] = b; if (H == 1) { a = pos[a].S, b = pos[b].S; if (a > b) swap(a, b); add(a); if (a + 1 < b) add(b); else add(b, 1); return tt.get(); } if (H <= 1000 && W <= 1000) { tx.upd(a, pos[a].F); tx.upd(b, pos[b].F); ty.upd(a, pos[a].S); ty.upd(b, pos[b].S); int pos = 1, cnt = 0; while (true) { int npos = get(pos); if (npos == pos) { cnt++; } pos = npos + (pos == npos); if (pos > S) break; } return cnt; } for (int i = a; i <= b; ++i) { if ((rx[i] - lx[i] + 1) * (ry[i] - ly[i] + 1) == i) ans--; rx[i] = max(rx[i - 1], pos[i].F); lx[i] = min(lx[i - 1], pos[i].F); ry[i] = max(ry[i - 1], pos[i].S); ly[i] = min(ly[i - 1], pos[i].S); if ((rx[i] - lx[i] + 1) * (ry[i] - ly[i] + 1) == i) ans++; } return ans; }

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

seats.cpp: In member function 'void tree_line::build(int, int, int)':
seats.cpp:38:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
seats.cpp: In member function 'void tree_line::out(int, int, int)':
seats.cpp:49:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
seats.cpp: In member function 'void tree_line::upd(int, int, int, int, int, int)':
seats.cpp:69:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
#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...