제출 #569326

#제출 시각아이디문제언어결과실행 시간메모리
569326ngpin04자리 배치 (IOI18_seats)C++17
37 / 100
2474 ms257020 KiB
#include "seats.h" #include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define TASK "" #define bit(x) (1LL << (x)) #define getbit(x, i) (((x) >> (i)) & 1) #define ALL(x) (x).begin(), (x).end() using namespace std; template <typename T1, typename T2> bool mini(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maxi(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { return l + rd() % (r - l + 1); } const int N = 1e6 + 5; const int oo = 1e9; const long long ooo = 1e18; const int mod = 1e9 + 7; // 998244353; const long double pi = acos(-1); typedef tuple <int, int, int, int> pir; pair <int, int> st[N << 2]; int lz[N << 2]; set <int> sr[N], sc[N]; int minx[N]; int miny[N]; int maxx[N]; int maxy[N]; int x[N]; int y[N]; int a[N]; int n,m,sz,ans; void dolazy(int id) { for (int i = (id << 1); i <= (id << 1 | 1); i++) { lz[i] += lz[id]; st[i].fi += lz[id]; } } void build(int id, int l, int r) { if (l == r) { st[id].se = 1; return; } int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); } void update(int id, int l, int r, int u, int v, int val) { if (l > v || r < u) return; if (l >= u && r <= v) { lz[id] += val; st[id].fi += val; return; } int mid = (l + r) >> 1; dolazy(id); update(id << 1, l, mid, u, v, val); update(id << 1 | 1, mid + 1, r, u, v, val); st[id] = st[id << 1]; if (mini(st[id].fi, st[id << 1 | 1].fi)) st[id] = st[id << 1 | 1]; else if (st[id].fi == st[id << 1 | 1].fi) st[id].se += st[id << 1 | 1].se; } void update(int l, int r, int val) { update(1, 0, sz - 1, l, r, val); } int getmin() { return st[1].se; } bool check(int i) { int dx = maxx[i] - minx[i] + 1; int dy = maxy[i] - miny[i] + 1; return (dx * dy == i + 1); } void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { n = H; m = W; sz = n * m; build(1, 0, sz - 1); for (int i = 0; i < n * m; i++) { x[i] = R[i], y[i] = C[i]; sr[x[i]].insert(i); sc[y[i]].insert(i); minx[i] = maxx[i] = x[i]; miny[i] = maxy[i] = y[i]; a[y[i]] = i; } for (int i = 0; i + 1 < n * m; i++) update(max(a[i], a[i + 1]), sz - 1, -1); for (int i = 0; i < n * m; i++) { if (i > 0) { mini(minx[i], minx[i - 1]); mini(miny[i], miny[i - 1]); maxi(maxx[i], maxx[i - 1]); maxi(maxy[i], maxy[i - 1]); } ans += check(i); } for (int i = 0; i < sz; i++) update(i, i, i); } int sub2() { vector <int> events; for (int i = 0; i < n; i++) events.push_back(*sr[i].begin()); for (int i = 0; i < m; i++) events.push_back(*sc[i].begin()); sort(ALL(events)); int minx = oo, maxx = -oo, miny = oo, maxy = -oo; int res = 0; for (int it = 0; it < (int) events.size(); it++) { if (it + 1 == (int) events.size()) { res++; break; } int i = events[it]; int j = events[it + 1]; mini(minx, x[i]); mini(miny, y[i]); maxi(maxx, x[i]); maxi(maxy, y[i]); int t = (maxx - minx + 1) * (maxy - miny + 1); res += (i <= t && t <= j); } return res; } int sub3(int l, int r) { if (l > r) swap(l, r); for (int i = l; i <= r; i++) { ans -= check(i); minx[i] = maxx[i] = x[i]; miny[i] = maxy[i] = y[i]; if (i > 0) { mini(minx[i], minx[i - 1]); mini(miny[i], miny[i - 1]); maxi(maxx[i], maxx[i - 1]); maxi(maxy[i], maxy[i - 1]); } ans += check(i); } return ans; } void add(int i, int val) { int pos = y[i]; if (pos > 0) update(max(a[pos - 1], a[pos]), sz - 1, val); if (pos + 1 < sz) update(max(a[pos], a[pos + 1]), sz - 1, val); } int sub4() { return getmin(); } int swap_seats(int l, int r) { sr[x[l]].erase(l); sr[x[r]].erase(r); sc[y[l]].erase(l); sc[y[r]].erase(r); add(l, 1); add(r, 1); swap(x[l], x[r]); swap(y[l], y[r]); swap(a[y[l]], a[y[r]]); add(l, -1); add(r, -1); sr[x[l]].insert(l); sr[x[r]].insert(r); sc[y[l]].insert(l); sc[y[r]].insert(r); if (max(n, m) <= 1000) return sub2(); if (abs(l - r) <= 10000) return sub3(l, r); if (n == 1) return sub4(); return -1; } //#include "grader.cpp"
#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...