(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

Submission #412700

#TimeUsernameProblemLanguageResultExecution timeMemory
412700usachevd0Seats (IOI18_seats)C++14
100 / 100
3782 ms104528 KiB
#include <bits/stdc++.h> #ifndef LOCAL #include "seats.h" #endif using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back #define all(a) (a).begin(), (a).end() #define Time (clock() * 1.0 / CLOCKS_PER_SEC) using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using pil = pair<int, ll>; using pli = pair<ll, int>; using pll = pair<ll, ll>; using ld = long double; template<typename T1, typename T2> bool chkmin(T1& x, T2 y) { return y < x ? (x = y, true) : false; } template<typename T1, typename T2> bool chkmax(T1& x, T2 y) { return y > x ? (x = y, true) : false; } void debug_out() { cerr << endl; } template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); } template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n) #else #define debug(...) 1337 #define mdebug(a, n) 1337 #endif template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) { for (auto& x : v) stream << x << ' '; return stream; } template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; } const int INF32 = 1e9; const int maxN = 1e6 + 6; const int Dx[4] = {1, 0, -1, 0}; const int Dy[4] = {0, 1, 0, -1}; int N, M, S; int X[maxN], Y[maxN]; vector<int> grid[maxN]; const int logN = 20; const int NN = 1 << logN; int lazy[2 * NN]; int mn[2 * NN], cnt[2 * NN]; bool valid(int x, int y) { return 1 <= x && x <= N && 1 <= y && y <= M; } void init(int v, int vl, int vr) { lazy[v] = 0; mn[v] = 0; cnt[v] = vr - vl + 1; if (vl != vr) { int vm = (vl + vr) >> 1; init(v << 1, vl, vm); init(v << 1 | 1, vm + 1, vr); } } void apply(int v, int delta) { mn[v] += delta; lazy[v] += delta; } void push(int v) { if (!lazy[v]) return; apply(v << 1, lazy[v]); apply(v << 1 | 1, lazy[v]); lazy[v] = 0; } void upd(int v) { mn[v] = mn[v << 1]; cnt[v] = cnt[v << 1]; if (mn[v << 1 | 1] < mn[v]) { mn[v] = mn[v << 1 | 1]; cnt[v] = cnt[v << 1 | 1]; } else if (mn[v << 1 | 1] == mn[v]) { cnt[v] += cnt[v << 1 | 1]; } } void add(int v, int vl, int vr, int l, int r, int delta) { if (l > r || vr < l || r < vl) return; if (l <= vl && vr <= r) { apply(v, delta); return; } int vm = (vl + vr) >> 1; push(v); add(v << 1, vl, vm, l, r, delta); add(v << 1 | 1, vm + 1, vr, l, r, delta); upd(v); } void add(int l, int r, int delta) { chkmax(l, 1); chkmin(r, S); if (l > r) return; add(1, 1, S, l, r, delta); } void rec(int x, int y, int d, int delta) { if (!valid(x, y)) return; //debug(x, y, d, delta); int x1 = x + Dx[d], y1 = y + Dy[d]; int x2 = x + Dx[(d + 1) % 4], y2 = y + Dy[(d + 1) % 4]; int x3 = x + Dx[d] + Dx[(d + 1) % 4], y3 = y + Dy[d] + Dy[(d + 1) % 4]; int v = grid[x][y]; int v1 = grid[x1][y1]; int v2 = grid[x2][y2]; int v3 = grid[x3][y3]; add(max(v1, v2), v - 1, delta); if (d == 0) add(v, min({v1, v2, v3}) - 1, delta); } int gt() { if (mn[1] == 1) return cnt[1]; return 0; } void give_initial_chart(int _N, int _M, vector<int> _X, vector<int> _Y) { N = _N, M = _M; S = N * M; for (int x = 0; x <= N + 2; ++x) grid[x].assign(M + 3, INF32); for (int i = 1; i <= N * M; ++i) { X[i] = _X[i - 1] + 1; Y[i] = _Y[i - 1] + 1; grid[X[i]][Y[i]] = i; } init(1, 1, S); for (int x = 1; x <= N; ++x) for (int y = 1; y <= M; ++y) for (int d = 0; d < 4; ++d) rec(x, y, d, 1); } int swap_seats(int a, int b) { ++a; ++b; vector<pair<pii, int>> to_rec; for (int i : {a, b}) { int x = X[i], y = Y[i]; for (int d = 0; d < 4; ++d) { to_rec.push_back({{x, y}, d}); int x1 = x + Dx[d], y1 = y + Dy[d]; if (valid(x1, y1)) { for (int u = 1; u <= 2; ++u) { to_rec.push_back({{x1, y1}, (d + u) % 4}); } } int x3 = x + Dx[d] + Dx[(d + 1) % 4], y3 = y + Dy[d] + Dy[(d + 1) % 4]; if (valid(x3, y3)) to_rec.push_back({{x3, y3}, d ^ 2}); } } sort(all(to_rec)); to_rec.resize(unique(all(to_rec)) - to_rec.begin()); for (auto& e : to_rec) { rec(e.fi.fi, e.fi.se, e.se, -1); } swap(X[a], X[b]); swap(Y[a], Y[b]); grid[X[a]][Y[a]] = a; grid[X[b]][Y[b]] = b; for (auto& e : to_rec) { rec(e.fi.fi, e.fi.se, e.se, 1); } return gt(); } #ifdef LOCAL int read_int() { int x; if (scanf("%d", &x) != 1) { fprintf(stderr, "Error while reading input\n"); exit(1); } return x; } int32_t main() { #ifdef LOCAL freopen("in", "r", stdin); #endif ios::sync_with_stdio(0); cin.tie(0); int H = read_int(); int W = read_int(); int Q = read_int(); std::vector<int> R(H * W), C(H * W); for (int i = 0; i < H * W; ++i) { R[i] = read_int(); C[i] = read_int(); } std::vector<int> A(Q), B(Q); for (int j = 0; j < Q; ++j) { A[j] = read_int(); B[j] = read_int(); } give_initial_chart(H, W, R, C); for (int j = 0; j < Q; ++j) { int answer = swap_seats(A[j], B[j]); printf("%d\n", answer); } return 0; } #endif
#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...