Submission #103044

#TimeUsernameProblemLanguageResultExecution timeMemory
103044KCSCSeats (IOI18_seats)C++14
70 / 100
4083 ms125688 KiB
#ifndef HOME #include "seats.h" #endif #include <bits/stdc++.h> using namespace std; #ifdef HOME namespace { int read_int() { int x; if (scanf("%d", &x) != 1) { fprintf(stderr, "Error while reading input\n"); exit(1); } return x; } } // namespace #endif const int DIM = 1000005; struct Node { int mnm, cnt, lzy; Node(int _mnm = 0, int _cnt = 0, int _lzy = 0) : mnm(_mnm), cnt(_cnt), lzy(_lzy) {} } sgt[DIM << 2]; vector<vector<int>> mat; pair<int, int> pos[DIM]; int n, m; inline void updateLazy(int nd, int le, int ri) { if (sgt[nd].lzy) { sgt[nd].mnm += sgt[nd].lzy; if (le != ri) { sgt[nd << 1].lzy += sgt[nd].lzy; sgt[nd << 1 | 1].lzy += sgt[nd].lzy; } sgt[nd].lzy = 0; } } void build(int nd, int le, int ri) { sgt[nd].cnt = ri - le + 1; if (le != ri) { int md = (le + ri) >> 1; build(nd << 1, le, md); build(nd << 1 | 1, md + 1, ri); } } int _st, _en, _vl; void update(int nd, int le, int ri) { updateLazy(nd, le, ri); if (ri < _st or _en < le or _st > _en) { return; } if (_st <= le and ri <= _en) { sgt[nd].lzy += _vl; updateLazy(nd, le, ri); } else { int md = (le + ri) >> 1; update(nd << 1, le, md); update(nd << 1 | 1, md + 1, ri); sgt[nd].mnm = min(sgt[nd << 1].mnm, sgt[nd << 1 | 1].mnm); sgt[nd].cnt = 0; if (sgt[nd].mnm == sgt[nd << 1].mnm) { sgt[nd].cnt += sgt[nd << 1].cnt; } if (sgt[nd].mnm == sgt[nd << 1 | 1].mnm) { sgt[nd].cnt += sgt[nd << 1 | 1].cnt; } } } void updateSquare(int x, int y, int vl = 1) { vector<int> arr; arr.push_back(mat[x][y]); arr.push_back(mat[x + 1][y + 1]); arr.push_back(mat[x][y + 1]); arr.push_back(mat[x + 1][y]); sort(arr.begin(), arr.end()); _st = arr[0]; _en = arr[1] - 1; _vl = vl * 1; update(1, 0, n * m - 1); _st = arr[2]; _en = arr[3] - 1; _vl = vl * 5; update(1, 0, n * m - 1); } void give_initial_chart(int h, int w, vector<int> R, vector<int> C) { n = h; m = w; mat.resize(n + 2, vector<int>(m + 2, n * m)); for (int i = 0; i < n * m; ++i) { ++R[i]; ++C[i]; mat[R[i]][C[i]] = i; pos[i] = make_pair(R[i], C[i]); } build(1, 0, n * m - 1); for (int i = 0; i <= n; ++i) { for (int j = 0; j <= m; ++j) { updateSquare(i, j); } } } int swap_seats(int a, int b) { set<pair<int, int>> sqr; for (int i = -1; i <= 0; ++i) { for (int j = -1; j <= 0; ++j) { sqr.insert(make_pair(pos[a].first + i, pos[a].second + j)); sqr.insert(make_pair(pos[b].first + i, pos[b].second + j)); } } for (auto sq : sqr) { updateSquare(sq.first, sq.second, -1); } swap(mat[pos[a].first][pos[a].second], mat[pos[b].first][pos[b].second]); swap(pos[a], pos[b]); for (auto sq : sqr) { updateSquare(sq.first, sq.second, 1); } return sgt[1].mnm == 4 ? sgt[1].cnt : 0; } #ifdef HOME int main() { freopen("seats.in", "r", stdin); freopen("seats.out", "w", stdout); 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...