Submission #835727

#TimeUsernameProblemLanguageResultExecution timeMemory
835727JohannSeats (IOI18_seats)C++14
17 / 100
4072 ms76584 KiB
#include "seats.h" #include "bits/stdc++.h" using namespace std; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> pii; typedef vector<pii> vpii; #define sz(x) (int)(x).size() #define all(x) (x).begin(), (x).end() int H, W; std::vector<int> R, C; struct segtree { int size; vpii arr; const pii NEUTRAL = {1 << 30, -(1 << 30)}; void init(vi &A) { size = 1; while (size < sz(A)) size *= 2; arr.assign(2 * size, NEUTRAL); for (int i = 0; i < sz(A); ++i) arr[i + size] = {A[i], A[i]}; for (int i = size - 1; i > 0; --i) arr[i] = combine(arr[2 * i], arr[2 * i + 1]); } pii combine(const pii &a, const pii &b) { return {min(a.first, b.first), max(a.second, b.second)}; } void set(int i, int v) { i += size; arr[i] = {v, v}; i /= 2; while (i > 0) { arr[i] = combine(arr[2 * i], arr[2 * i + 1]); i /= 2; } } pii query(int l, int r) { return query(l, r, 1, 0, size); } pii query(int l, int r, int x, int lx, int rx) { if (l <= lx && rx <= r) return arr[x]; if (r <= lx || rx <= l) return NEUTRAL; int m = (lx + rx) / 2; pii left = query(l, r, 2 * x, lx, m); pii right = query(l, r, 2 * x + 1, m, rx); return combine(left, right); } }; segtree segR; segtree segC; struct fenwick { vi arr; void init(int size) { arr.assign(size + 1, 0); } void add(int i, int v) { ++i; while (i < sz(arr)) arr[i] += v, i += i & (~i + 1); } int query(int l, int r) { return query(r - 1) - ((l > 0) ? query(l - 1) : 0); } int query(int i) { ++i; int ans = 0; while (i > 0) ans += arr[i], i -= i & (~i + 1); return ans; } }; fenwick fen; void give_initial_chart(int _H, int _W, std::vector<int> _R, std::vector<int> _C) { H = _H, W = _W; R = _R, C = _C; segR.init(R), segC.init(C); fen.init(H * W); int rmax = R[0], rmin = R[0]; int cmax = C[0], cmin = C[0]; int k = 0; while (k < H * W) { tie(rmin, rmax) = segR.query(0, k + 1); tie(cmin, cmax) = segC.query(0, k + 1); int area = (rmax - rmin + 1) * (cmax - cmin + 1); if (area == k + 1) fen.add(k, 1), ++k; else { assert(area - 1 > k); k = area - 1; } } } int swap_seats(int a, int b) { if (a > b) swap(a, b); swap(R[a], R[b]), swap(C[a], C[b]); segR.set(a, R[a]); segC.set(a, C[a]); segR.set(b, R[b]); segC.set(b, C[b]); int rmin, rmax, cmin, cmax; tie(rmin, rmax) = segR.query(0, a + 1); tie(cmin, cmax) = segC.query(0, a + 1); for (int k = a; k < b + 1; ++k) { if (fen.query(k, k + 1)) fen.add(k, -1); rmax = max(rmax, R[k]); rmin = min(rmin, R[k]); cmax = max(cmax, C[k]); cmin = min(cmin, C[k]); int area = (rmax - rmin + 1) * (cmax - cmin + 1); if (area == k + 1) fen.add(k, 1); } return fen.query(0, H * W); }
#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...