제출 #121274

#제출 시각아이디문제언어결과실행 시간메모리
121274SirCeness자리 배치 (IOI18_seats)C++17
11 / 100
4102 ms253560 KiB
#include <bits/stdc++.h> #define pb push_back #define mp make_pair #define inf 1000000009 using namespace std; typedef long long ll; map<pair<int, int>, int> mapp; int tmp[4]; int MX; vector<int> R; vector<int> C; int lazy[4000006]; int minn[4000006]; int countt[4000006]; void stc(int node, int l, int r){ if (l == r){ minn[node] = 0; countt[node] = 1; lazy[node] = 0; } else { int m = (l+r)/2; stc(node*2, l, m); stc(node*2+1, m+1, r); minn[node] = min(minn[node*2], minn[node*2+1]); countt[node] = 0; if (minn[node] == minn[node*2]) countt[node] += countt[node*2]; if (minn[node] == minn[node*2+1]) countt[node] += countt[node*2+1]; lazy[node] = 0; } } int get(int node){ return minn[node] + lazy[node]; } void push(int node){ minn[node] += lazy[node]; lazy[node*2+1] += lazy[node]; lazy[node*2] += lazy[node]; lazy[node] = 0; } void stu(int node, int l, int r, int sl, int sr, int val){ if (sl <= l && r <= sr){ lazy[node] += val; } else if (r < sl ||sr < l){ return; } else { int m = (l+r)/2; push(node); stu(node*2, l, m, sl, sr, val); stu(node*2+1, m+1, r, sl, sr, val); minn[node] = min(get(node*2), get(node*2+1)); countt[node] = 0; if (minn[node] == get(node*2)) countt[node] += countt[node*2]; if (minn[node] == get(node*2+1)) countt[node] += countt[node*2+1]; } } void yap(int i, int j){ tmp[0] = mapp[mp(i, j)]; tmp[1] = mapp[mp(i+1, j)]; tmp[2] = mapp[mp(i, j+1)]; tmp[3] = mapp[mp(i+1, j+1)]; sort(tmp, tmp+4); //cout << "yap: " << tmp[0] << ", " << tmp[1] << ", " << tmp[2] << ", " << tmp[3] << endl; if (tmp[0] < tmp[1]) stu(1, 0, MX-1, tmp[0], tmp[1]-1, +1); if (tmp[2] < tmp[3]) stu(1, 0, MX-1, tmp[2], tmp[3]-1, +1); //if (tmp[0] < tmp[1]) cout << tmp[0] << " - " << tmp[1]-1 << ": +1" << endl; //if (tmp[2] < tmp[3]) cout << tmp[2] << " - " << tmp[3]-1 << ": +1" << endl; } void boz(int i, int j){ tmp[0] = mapp[mp(i, j)]; tmp[1] = mapp[mp(i+1, j)]; tmp[2] = mapp[mp(i, j+1)]; tmp[3] = mapp[mp(i+1, j+1)]; sort(tmp, tmp+4); if (tmp[0] != -1) stu(1, 0, MX-1, tmp[0], tmp[1]-1, -1); if (tmp[2] != -1) stu(1, 0, MX-1, tmp[2], tmp[3]-1, -1); } int getnode(int node, int l, int r, int ind){ if (l == r) return get(node); else { int m = (l+r)/2; push(node); if (ind <= m) return getnode(node*2, l, m, ind); else return getnode(node*2+1, m+1, r, ind); } } void give_initial_chart(int H, int W, vector<int> RR, vector<int> CC) { R = RR; C = CC; MX = H*W; for (int i = 0; i < H*W; i++){ mapp[mp(R[i], C[i])] = i; } for (int i = -1; i <= H; i++){ for (int j = -1; j <= W; j++){ if (i == -1 || j == -1 || i == H ||j == W) mapp[mp(i, j)] = MX; } } stc(1, 0, MX-1); for (int i = -1; i < H; i++){ for (int j = -1; j < W; j++){ yap(i, j); } } /*for (int i = 0; i < MX; i++) cout << getnode(1, 0, MX-1, i) << " "; cout << endl;*/ } int swap_seats(int a, int b) { int i1 = R[a]; int j1 = C[a]; int i2 = R[b]; int j2 = C[b]; boz(i1-1, j1-1); boz(i1-1, j1); boz(i1, j1-1); boz(i1, j1); boz(i2-1, j2-1); boz(i2-1, j2); boz(i2, j2-1); boz(i2, j2); R[a] = i2; R[b] = i1; C[a] = j2; C[b] = j1; mapp[mp(i1, j1)] = b; mapp[mp(i2, j2)] = a; yap(i1, j1); yap(i1, j1-1); yap(i1-1, j1); yap(i1-1, j1-1); yap(i2, j2); yap(i2, j2-1); yap(i2-1, j2); yap(i2-1, j2-1); return countt[1]; } /* int main(){ freopen("stl.gir", "r", stdin); int h, w; cin >> h >> w; vector<int> r; vector<int> c; for (int i = 0; i < h*w; i++){ int a, b; cin >> a >> b; r.pb(a); c.pb(b); } give_initial_chart(h, w, r, c); int q; cin >> q; while(q--){ int a, b; cin >> a >> b; cout << swap_seats(a, b) << endl; } } */
#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...