제출 #835144

#제출 시각아이디문제언어결과실행 시간메모리
835144Johann자리 배치 (IOI18_seats)C++14
0 / 100
290 ms98956 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 = sz(A) - 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}; while (i >>= 1 > 0) arr[i] = combine(arr[2 * i], arr[2 * i + 1]); } 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; 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); } int swap_seats(int a, int 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 rmax = R[0], rmin = R[0]; int cmax = C[0], cmin = C[0]; int ans = 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) ++ans, ++k; else { assert(area - 1 > k); k = area - 1; } } return 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...