제출 #596328

#제출 시각아이디문제언어결과실행 시간메모리
596328AlperenT자리 배치 (IOI18_seats)C++17
11 / 100
4081 ms56892 KiB
#include <bits/stdc++.h> #include "seats.h" using namespace std; const int N = 1e6 + 5, INF = 1e9 + 5; int n, h, w; pair<int, int> merge(pair<int, int> a, pair<int, int> b){ return {min(a.first, b.first), max(a.second, b.second)}; } struct SegTree{ pair<int, int> tree[N * 4]; void build(vector<int> &arr, int v = 1, int l = 0, int r = n - 1){ if(l == r) tree[v] = {arr[l], arr[l]}; else{ int m = l + (r - l) / 2; build(arr, v * 2, l, m); build(arr, v * 2 + 1, m + 1, r); tree[v] = merge(tree[v * 2], tree[v * 2 + 1]); } } pair<int, int> query(int l, int r, int v = 1, int tl = 0, int tr = n - 1){ if(l > r) return {INF, -INF}; else if(l == tl && r == tr) return tree[v]; else{ int tm = tl + (tr - tl) / 2; return merge(query(l, min(tm, r), v * 2, tl, tm), query(max(tm + 1, l), r, v * 2 + 1, tm + 1, tr)); } } void update(int pos, int val, int v = 1, int l = 0, int r = n - 1){ if(l == r) tree[v] = {val, val}; else{ int m = l + (r - l) / 2; if(pos <= m) update(pos, val, v * 2, l, m); else update(pos, val, v * 2 + 1, m + 1, r); tree[v] = merge(tree[v * 2], tree[v * 2 + 1]); } } }; SegTree sgtx, sgty; vector<int> X, Y; void give_initial_chart(int H, int W, vector<int> X_, vector<int> Y_) { X = X_, Y = Y_; h = H, w = W; n = H * W; sgtx.build(X); sgty.build(Y); } int swap_seats(int a, int b){ sgtx.update(a, X[b]); sgty.update(a, Y[b]); sgtx.update(b, X[a]); sgty.update(b, Y[a]); swap(X[a], X[b]); swap(Y[a], Y[b]); int ans = 0; if(max(h, w) <= 1000){ pair<int, int> x, y; int cur = 0; while(cur < n){ x = sgtx.query(0, cur); y = sgty.query(0, cur); if((x.second - x.first + 1) * (y.second - y.first + 1) == cur + 1) ans++, cur++; else cur = (x.second - x.first + 1) * (y.second - y.first + 1) - 1; } } else{ pair<int, int> x = {INF, -INF}, y = {INF, -INF}; for(int i = 0; i < n; i++){ x = merge(x, {X[i], X[i]}); y = merge(y, {Y[i], Y[i]}); if((x.second - x.first + 1) * (y.second - y.first + 1) == i + 1) ans++; } } 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...