제출 #294197

#제출 시각아이디문제언어결과실행 시간메모리
294197Kastanda자리 배치 (IOI18_seats)C++11
37 / 100
4049 ms103412 KiB
// M #include<bits/stdc++.h> #include "seats.h" #define pb push_back #define lc (id << 1) #define rc (lc ^ 1) #define md ((l + r) >> 1) using namespace std; const int MXN = 1e6 + 10; int n, m, k, R[MXN], C[MXN]; int MN[MXN * 4], LZ[MXN * 4], Cnt[MXN * 4]; vector < vector < int > > A; void Build(int id = 1, int l = 0, int r = k) { Cnt[id] = r - l; if (r - l < 2) return ; Build(lc, l, md); Build(rc, md, r); } inline void Shift(int id) { MN[lc] += LZ[id]; MN[rc] += LZ[id]; LZ[lc] += LZ[id]; LZ[rc] += LZ[id]; LZ[id] = 0; } void Add(int le, int ri, int val, int id = 1, int l = 0, int r = k) { if (ri <= l || r <= le) return ; if (le <= l && r <= ri) { MN[id] += val; LZ[id] += val; return ; } Shift(id); Add(le, ri, val, lc, l, md); Add(le, ri, val, rc, md, r); MN[id] = min(MN[lc], MN[rc]); Cnt[id] = 0; if (MN[id] == MN[lc]) Cnt[id] += Cnt[lc]; if (MN[id] == MN[rc]) Cnt[id] += Cnt[rc]; } inline void Do(int i, int j, int val) { vector < int > tmp = {A[i][j], A[i + 1][j], A[i][j + 1], A[i + 1][j + 1]}; sort(tmp.begin(), tmp.end()); Add(tmp[0], tmp[1], val); Add(tmp[2], tmp[3], val); } void give_initial_chart(int _H, int _W, vector < int > _R, vector < int > _C) { n = _H; m = _W; for (int i = 0; i < n * m; i ++) R[i] = _R[i], C[i] = _C[i]; k = n * m; for (int i = 0; i <= n + 1; i ++) A.pb(vector < int > (m + 2, k)); for (int i = 0; i < k; i ++) R[i] ++, C[i] ++; for (int i = 0; i < k; i ++) A[R[i]][C[i]] = i; Build(); for (int i = 0; i <= n; i ++) for (int j = 0; j <= m; j ++) Do(i, j, 1); } int swap_seats(int a, int b) { vector < pair < int , int > > vec; for (int dx = -1; dx <= 0; dx ++) for (int dy = -1; dy <= 0; dy ++) vec.push_back({R[a] + dx, C[a] + dy}), vec.push_back({R[b] + dx, C[b] + dy}); sort(vec.begin(), vec.end()); vec.resize(unique(vec.begin(), vec.end()) - vec.begin()); for (auto X : vec) Do(X.first, X.second, -1); swap(R[a], R[b]); swap(C[a], C[b]); swap(A[R[a]][C[a]], A[R[b]][C[b]]); for (auto X : vec) Do(X.first, X.second, 1); assert(MN[1] == 4); return Cnt[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...