제출 #792942

#제출 시각아이디문제언어결과실행 시간메모리
7929421bin자리 배치 (IOI18_seats)C++14
31 / 100
1721 ms53900 KiB
#include <bits/stdc++.h> //#include "seats.h" #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") using namespace std; #define all(v) v.begin(), v.end() typedef long long ll; const int b = 1 << 20; int n, lazy[b * 2], W, v[b]; pair<int, int> seg[b * 2]; vector<int> Y, X; void upd_lazy(int ix, int l, int r){ if(l < n && seg[ix].first == b) seg[ix] = {0, min(n - 1, r) - l + 1}; if(!lazy[ix]) return; 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 ix, int p){ vector<int> t; for(int i = -1; i <= 0; i++) for(int j = -1; j <= 0; j++) t.emplace_back(v[ix + i * (W + 2) + 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); return; } void give_initial_chart(int H, int W_, vector<int> R, vector<int> C) { Y = R; X = C; W = W_; n = H * W; for(int i = 0; i < (H + 2) * (W + 2); i++) v[i] = n; for(int i = 0; i < n; i++) v[++Y[i] * (W + 2) + ++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 * (W + 2) + 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) * (W + 2) + X[i1] + j, -1); calc((Y[i2] + i) * (W + 2) + X[i2] + j, -1); } swap(Y[i1], Y[i2]); swap(X[i1], X[i2]); swap(v[Y[i1] * (W + 2) + X[i1]], v[Y[i2] * (W + 2) + X[i2]]); for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++){ calc((Y[i1] + i) * (W + 2) + X[i1] + j, 1); calc((Y[i2] + i) * (W + 2) + X[i2] + j, 1); } if(seg[1].first == 4) return seg[1].second; 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...