Submission #798444

#TimeUsernameProblemLanguageResultExecution timeMemory
798444TheSahibSeats (IOI18_seats)C++14
0 / 100
4062 ms262144 KiB
#include "seats.h" #include <bits/stdc++.h> #define ll long long #define pii pair<int, int> using namespace std; const int MAX = 1e6 + 5; const int BLOCK = 5; const int BLOCKCNT = MAX / BLOCK + 3; const int oo = 1e9 + 9; int n; int h, w; pii mp[MAX]; struct DATA{ map<int, int> mpX, mpY; void add(pii a){ mpX[a.first]++; mpY[a.second]++; } void remove(pii a){ mpX[a.first]--; if(mpX[a.first] == 0) mpX.erase(a.first); mpY[a.second]--; if(mpY[a.second] == 0) mpY.erase(a.second); } array<int, 4> get(){ return {mpX.begin()->first, mpY.begin()->first, prev(mpX.end())->first, prev(mpY.end())->first}; } }; DATA blocks[BLOCKCNT]; void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) { n = R.size(); h = H; w = W; for (int i = 0; i < n; i++) { mp[i] = {R[i], C[i]}; } int p = 0; for (int i = 0; i < n; i++) { blocks[p].add({R[i], C[i]}); if(i % BLOCK == 0){ ++p; blocks[p].mpX = blocks[p - 1].mpX; blocks[p].mpY = blocks[p - 1].mpY; } } } int swap_seats(int a, int b) { if(a > b) swap(a, b); int aBLOCK = (a + BLOCK - 1) / BLOCK * BLOCK; int bBLOCK = (b + BLOCK - 1) / BLOCK * BLOCK; for (int i = aBLOCK; i <= bBLOCK; i++) { blocks[i].remove(mp[a]); blocks[i].add(mp[b]); } swap(mp[a], mp[b]); int mnR = oo, mxR = -oo, mnC = oo, mxC = -oo; int ans = 0; for (int i = 0; i < n; i++) { if(i % BLOCK == 0){ array<int, 4> a = blocks[i / BLOCK].get(); mxR = max(mxR, a[2]); mxC = max(mxC, a[3]); mnR = min(mnR, a[0]); mnC = min(mnC, a[1]); } else{ mxR = max(mxR, mp[i].first); mxC = max(mxC, mp[i].second); mnR = min(mnR, mp[i].first); mnC = min(mnC, mp[i].second); } int r = mxR - mnR + 1; int c = mxC - mnC + 1; if(r * c == i + 1){ ans++; } if(r * c - (i + 1) >= BLOCK){ i = (i + BLOCK) / BLOCK * BLOCK - 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...