제출 #596908

#제출 시각아이디문제언어결과실행 시간메모리
596908Lucpp자리 배치 (IOI18_seats)C++17
37 / 100
4053 ms117828 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; const int INF = 1e9; struct MinSeg{ vector<int> seg; int cap; void init(vector<int> v){ for(cap = 1; cap < (int)v.size(); cap *= 2); seg.resize(2*cap, INF); for(int i = 0; i < (int)v.size(); i++) seg[i+cap] = v[i]; for(int i = cap-1; i >= 1; i--) seg[i] = min(seg[2*i], seg[2*i+1]); } int qry(int l, int r, int a, int b, int i){ if(l <= a && b <= r) return seg[i]; if(b < l || r < a) return INF; int m = (a+b)/2; return min(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1)); } int qry(int l, int r){return qry(l, r, 1, cap, 1);} void upd(int i, int v){ i += cap; seg[i] = v; while(i > 1){ i /= 2; seg[i] = min(seg[2*i], seg[2*i+1]); } } }; struct MaxSeg{ vector<int> seg; int cap; void init(vector<int> v){ for(cap = 1; cap < (int)v.size(); cap *= 2); seg.resize(2*cap, -INF); for(int i = 0; i < (int)v.size(); i++) seg[i+cap] = v[i]; for(int i = cap-1; i >= 1; i--) seg[i] = max(seg[2*i], seg[2*i+1]); } int qry(int l, int r, int a, int b, int i){ if(l <= a && b <= r) return seg[i]; if(b < l || r < a) return -INF; int m = (a+b)/2; return max(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1)); } int qry(int l, int r){return qry(l, r, 1, cap, 1);} void upd(int i, int v){ i += cap; seg[i] = v; while(i > 1){ i /= 2; seg[i] = max(seg[2*i], seg[2*i+1]); } } }; int n, W, H; vector<int> r, c; vector<bool> mem; int ans = 0; MinSeg scmi, srmi; MaxSeg scma, srma; vector<set<int>> byR, byC; vector<int> fr, fc; void give_initial_chart(int h, int w, vector<int> R, vector<int> C) { H = h, W = w; n = H*W; r = R; c = C; if(H <= 1000 && W <= 1000){ byR.resize(H); byC.resize(W); fr.assign(H, -1); fc.assign(W, -1); for(int i = 0; i < n; i++){ byR[r[i]].insert(i), byC[c[i]].insert(i); if(fr[r[i]] == -1) fr[r[i]] = i; if(fc[c[i]] == -1) fc[c[i]] = i; } } else{ scmi.init(c); scma.init(c); srmi.init(r); srma.init(r); mem.resize(n); int cmi = INF, cma = -INF, rmi = INF, rma = -INF; for(int i = 0; i < n; i++){ cmi = min(cmi, c[i]); cma = max(cma, c[i]); rmi = min(rmi, r[i]); rma = max(rma, r[i]); if((cma-cmi+1)*(rma-rmi+1) == i+1) ans++, mem[i] = true; } } } int swap_seats(int a, int b) { if(a > b) swap(a, b); swap(r[a], r[b]); swap(c[a], c[b]); if(H <= 1000 && W <= 1000){ byR[r[a]].erase(b); byR[r[b]].erase(a); byR[r[a]].insert(a); byR[r[b]].insert(b); byC[c[a]].erase(b); byC[c[b]].erase(a); byC[c[a]].insert(a); byC[c[b]].insert(b); fr[r[a]] = *byR[r[a]].begin(); fr[r[b]] = *byR[r[b]].begin(); fc[c[a]] = *byC[c[a]].begin(); fc[c[b]] = *byC[c[b]].begin(); vector<int> ncmi(W), ncma(W), nrmi(H), nrma(H); int val = INF; for(int i = 0; i < W; i++){ ncmi[i] = val; val = min(val, fc[i]); } val = INF; for(int i = W-1; i >= 0; i--){ ncma[i] = val; val = min(val, fc[i]); } val = INF; for(int i = 0; i < H; i++){ nrmi[i] = val; val = min(val, fr[i]); } val = INF; for(int i = H-1; i >= 0; i--){ nrma[i] = val; val = min(val, fr[i]); } ans = 1; int cmi = c[0], cma = c[0], rmi = r[0], rma = r[0]; while(true){ int j = min(min(ncmi[cmi], ncma[cma]), min(nrmi[rmi], nrma[rma])); if(j == INF) break; cmi = min(cmi, c[j]); cma = max(cma, c[j]); rmi = min(rmi, r[j]); rma = max(rma, r[j]); int k = min(min(ncmi[cmi], ncma[cma]), min(nrmi[rmi], nrma[rma])); if(k == INF || (rma-rmi+1)*(cma-cmi+1) == k) ans++; } return ans; } else{ scmi.upd(a, c[a]); scma.upd(a, c[a]); srmi.upd(a, r[a]); srma.upd(a, r[a]); scmi.upd(b, c[b]); scma.upd(b, c[b]); srmi.upd(b, r[b]); srma.upd(b, r[b]); int cmi = scmi.qry(1, a), cma = scma.qry(1, a), rmi = srmi.qry(1, a), rma = srma.qry(1, a); for(int i = a; i < b; i++){ cmi = min(cmi, c[i]); cma = max(cma, c[i]); rmi = min(rmi, r[i]); rma = max(rma, r[i]); bool ok = ((cma-cmi+1)*(rma-rmi+1) == i+1); if(mem[i] && !ok) ans--; if(!mem[i] && ok) ans++; mem[i] = ok; } return ans; } }
#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...