제출 #792028

#제출 시각아이디문제언어결과실행 시간메모리
7920281bin자리 배치 (IOI18_seats)C++14
53 / 100
3072 ms77000 KiB
#include <bits/stdc++.h> #include "seats.h" using namespace std; #define all(v) v.begin(), v.end() typedef long long ll; const int b = 1 << 20; int n, lazy[b * 2]; pair<int, int> seg[b * 2]; vector<int> Y, X; vector<vector<int>> v; void upd_lazy(int ix, int l, int r){ if(!lazy[ix] || l >= n) return; if(seg[ix].first == b) seg[ix] = {0, min(n - 1, r) - l + 1}; seg[ix].first += lazy[ix]; if(l ^ r){ lazy[ix * 2] += lazy[ix]; lazy[ix * 2 + 1] += lazy[ix]; } lazy[ix] = 0; return; } void upd(int ix, int nl, int nr, int l, int r, int v){ upd_lazy(ix, nl, nr); if(nl > r || nr < l) return; if(nl >= l && nr <= r){ lazy[ix] += v; upd_lazy(ix, nl, nr); return; } int m = (nl + nr) / 2; upd(ix * 2, nl, m, l, r, v); upd(ix * 2 + 1, m + 1, nr, l, r, v); seg[ix].first = min(seg[ix * 2].first, seg[ix * 2 + 1].first); seg[ix].second = (seg[ix * 2].first == seg[ix].first ? seg[ix * 2].second : 0) + (seg[ix * 2 + 1].first == seg[ix].first ? seg[ix * 2 + 1].second : 0); return; } void calc(int y, int x, int p){ vector<int> t; for(int i = -1; i <= 0; i++) for(int j = -1; j <= 0; j++) t.emplace_back(v[y + i][x + j]); sort(all(t)); upd(1, 0, b - 1, t[0], t[1] - 1, p); upd(1, 0, b - 1, t[2], t[3] - 1, p); //for(int i = 0; i < n; i++) upd(1, 0, b - 1, i, i, 0); return; } void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { Y = R; X = C; n = H * W; v = vector<vector<int>> (H + 2, vector<int> (W + 2, n)); for(int i = 0; i < n; i++) v[++Y[i]][++X[i]] = i; for(int i = 1; i < b * 2; i++) seg[i].first = b; for(int i = 1; i <= H + 1; i++) for(int j = 1; j <= W + 1; j++) calc(i, j, 1); return; } int swap_seats(int i1, int i2) { for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++){ calc(Y[i1] + i, X[i1] + j, -1); calc(Y[i2] + i, X[i2] + j, -1); } swap(Y[i1], Y[i2]); swap(X[i1], X[i2]); swap(v[Y[i1]][X[i1]], v[Y[i2]][X[i2]]); for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++){ calc(Y[i1] + i, X[i1] + j, 1); calc(Y[i2] + i, X[i2] + j, 1); } //cout << seg[1].first << ' ' << seg[1].second << '\n'; if(seg[1].first == 4) return seg[1].second; return 0; } /* int main(void){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector<int> h(n * m), w(n * m); for(auto&i : h) cin >> i; for(auto&i : w) cin >> i; int q, a, b; give_initial_chart(n, m, h, w); cin >> q; while(q--){ cin >> a >> b; cout << swap_seats(a, b) << '\n'; } return 0; } */
#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...