제출 #835115

#제출 시각아이디문제언어결과실행 시간메모리
835115Johann자리 배치 (IOI18_seats)C++14
0 / 100
235 ms98984 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; vi mini, maxi; void init(vi &A) { size = 1; while (size < sz(A)) size *= 2; mini.assign(2 * size, INT_MAX); maxi.assign(2 * size, INT_MIN); for (int i = 0; i < sz(A); ++i) mini[i + size] = maxi[i + size] = A[i]; for (int i = sz(A) - 1; i > 0; --i) maxi[i] = max(maxi[2 * i], maxi[2 * i + 1]), mini[i] = min(mini[2 * i], mini[2 * i + 1]); } void set(int i, int v) { i += size; mini[i] = maxi[i] = v; while (i >>= 1 > 0) maxi[i] = max(maxi[2 * i], maxi[2 * i + 1]), mini[i] = min(mini[2 * i], mini[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 {mini[x], maxi[x]}; if (r <= lx || rx <= l) return {INT_MAX, INT_MIN}; int m = (lx + rx) / 2; int mini1, mini2, maxi1, maxi2; tie(mini1, maxi1) = query(l, r, 2 * x, lx, m); tie(mini2, maxi2) = query(l, r, 2 * x + 1, m, rx); return {min(mini1, mini2), max(maxi1, maxi2)}; } }; 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...