Submission #114125

#TimeUsernameProblemLanguageResultExecution timeMemory
114125Alexa2001Seats (IOI18_seats)C++17
31 / 100
4024 ms73860 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; const int Nmax = 1e6 + 5; int N, M, n; pair<int,int> where[Nmax]; int ans = 0, r1, c1, r2, c2, cnt, val; #define left_son (node<<1) #define right_son ((node<<1)|1) #define mid ((st+dr)>>1) class SegTree { int mxR[Nmax<<2], mxC[Nmax<<2], mnR[Nmax<<2], mnC[Nmax<<2]; void comb(int node, int x, int y) { mxR[node] = max(mxR[x], mxR[y]); mxC[node] = max(mxC[x], mxC[y]); mnR[node] = min(mnR[x], mnR[y]); mnC[node] = min(mnC[x], mnC[y]); } public: void init(int node, int st, int dr) { if(st == dr) { mxR[node] = mnR[node] = where[st].first; mxC[node] = mnC[node] = where[st].second; return; } init(left_son, st, mid); init(right_son, mid+1, dr); comb(node, left_son, right_son); } void update(int node, int st, int dr, int pos) { if(st == dr) { mxR[node] = mnR[node] = where[st].first; mxC[node] = mnC[node] = where[st].second; return; } if(pos <= mid) update(left_son, st, mid, pos); else update(right_son, mid+1, dr, pos); comb(node, left_son, right_son); } void query(int node, int st, int dr, int L, int R, int &r1, int &r2, int &c1, int &c2) { if(L <= st && dr <= R) { r1 = min(r1, mnR[node]); r2 = max(r2, mxR[node]); c1 = min(c1, mnC[node]); c2 = max(c2, mxC[node]); return; } if(L <= mid) query(left_son, st, mid, L, R, r1, r2, c1, c2); if(mid < R) query(right_son, mid+1, dr, L, R, r1, r2, c1, c2); } } aint; void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { int i; n = H * W; N = H; M = W; for(i=0; i < N * M; ++i) where[i] = {R[i], C[i]}; aint.init(1, 0, n-1); } void enlarge(int x, int y) { aint.query(1, 0, n-1, x, y, r1, r2, c1, c2); } int swap_seats(int x, int y) { swap(where[x], where[y]); aint.update(1, 0, n-1, x); aint.update(1, 0, n-1, y); ans = 0; val = 0; r1 = r2 = where[0].first; c1 = c2 = where[0].second; while(1) { if(val + 1 == (r2 - r1 + 1) * (c2 - c1 + 1)) { ++ans; ++val; if(val == n) return ans; enlarge(val, val); } else { int cnt = (r2 - r1 + 1) * (c2 - c1 + 1); enlarge(val + 1, cnt - 1); val = cnt - 1; } } assert(0); }
#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...