Submission #654328

#TimeUsernameProblemLanguageResultExecution timeMemory
654328buidangnguyen05Seats (IOI18_seats)C++17
17 / 100
4049 ms68548 KiB
//source: #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6 + 10; int row[N], col[N], ans[N]; int res; bool sub4 = 1; int n, m, q; vector<pair<int, int>> query; struct SegmentTree { int mx[4 * N], mi[4 * N]; void up(int s, int l, int r, int pos, int val) { if (l == r) { mx[s] = mi[s] = val; return; } int mid = (l + r) >> 1; if (pos <= mid) up(s << 1, l, mid, pos, val); else up(s << 1 | 1, mid + 1, r, pos, val); mx[s] = max(mx[s << 1], mx[s << 1 | 1]); mi[s] = min(mi[s << 1], mi[s << 1 | 1]); } pair<int, int> get(int s, int l, int r, int u, int v) { if (l > v || r < u || u > v) return make_pair(1e9, 0); if (l >= u && r <= v) return make_pair(mi[s], mx[s]); int mid = (l + r) >> 1; pair<int, int> L = get(s << 1, l, mid, u, v), R = get(s << 1 | 1, mid + 1, r, u, v); return make_pair(min(L.first, R.first), max(L.second, R.second)); } } R, C; int swap_seats(int x, int y) { if (x > y) swap(x, y); ++x; ++y; if (sub4 && y - x <= 1e4) { R.up(1, 1, m * n, x, row[y]); R.up(1, 1, m * n, y, row[x]); C.up(1, 1, m * n, x, col[y]); C.up(1, 1, m * n, y, col[x]); swap(row[x], row[y]); swap(col[x], col[y]); int miR, mxR, miC, mxC; tie(miR, mxR) = R.get(1, 1, m * n, 1, x - 1); tie(miC, mxC) = C.get(1, 1, m * n, 1, x - 1); for (int i = x; i <= y; ++i) { mxR = max(mxR, row[i]); miR = min(miR, row[i]); mxC = max(mxC, col[i]); miC = min(miC, col[i]); int nans = (mxR - miR + 1) * (mxC - miC + 1) == i; res += nans - ans[i]; ans[i] = nans; } return res; } else { sub4 = 0; R.up(1, 1, m * n, x, row[y]); R.up(1, 1, m * n, y, row[x]); C.up(1, 1, m * n, x, col[y]); C.up(1, 1, m * n, y, col[x]); swap(row[x], row[y]); swap(col[x], col[y]); int mxR = 0, miR = 1e9, mxC = 0, miC = 1e9; res = 0; for (int i = 1; i <= m * n; ++i) { tie(miR, mxR) = R.get(1, 1, m * n, 1, i); tie(miC, mxC) = C.get(1, 1, m * n, 1, i); if ((mxR - miR + 1) * (mxC - miC + 1) == i) ++res; else i = (mxR - miR + 1) * (mxC - miC + 1) - 1; } return res; } } void give_initial_chart(int H, int W, vector<int> _R, vector<int> _C) { m = H, n = W; for (int i = 1; i <= m * n; ++i) { row[i] = _R[i - 1]; col[i] = _C[i - 1]; ++row[i]; ++col[i]; } for (int i = 1; i <= m * n; ++i) { R.up(1, 1, m * n, i, row[i]); C.up(1, 1, m * n, i, col[i]); } int mxR = 0, miR = 1e9, mxC = 0, miC = 1e9; for (int i = 1; i <= m * n; ++i) { mxR = max(mxR, row[i]); miR = min(miR, row[i]); mxC = max(mxC, col[i]); miC = min(miC, col[i]); if ((mxR - miR + 1) * (mxC - miC + 1) == i) ans[i] = 1, ++res; } } // ඞඞඞඞඞ you sus
#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...