제출 #967133

#제출 시각아이디문제언어결과실행 시간메모리
967133jamesbamber자리 배치 (IOI18_seats)C++17
25 / 100
4099 ms74156 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; struct segment{ vector<int> mn, mx; int sz = 1; segment(){} segment(int n, vector<int> &v){ while(sz < n) sz*=2; mn.resize(2*sz, INT_MAX); for(int i=0; i<n; i++) mn[i+sz] = v[i]; for(int i=sz-1; i>0; i--) mn[i] = min(mn[2*i], mn[2*i+1]); mx.resize(2*sz, -1); for(int i=0; i<n; i++) mx[i+sz] = v[i]; for(int i=sz-1; i>0; i--) mx[i] = max(mx[2*i], mx[2*i+1]); } void upd(int id, int x){ int i = id + sz; mn[i] = x; for(i>>=1; i>0; i>>=1) mn[i] = min(mn[2*i], mn[2*i+1]); i = id + sz; mx[i] = x; for(i>>=1; i>0; i>>=1) mx[i] = max(mx[2*i], mx[2*i+1]); } pair<int,int> query(int lold, int rold){ int ansmn = INT_MAX; int l = lold, r = rold; for(l+=sz, r+=sz; l < r; l>>=1, r>>=1){ if(l&1) ansmn = min(ansmn, mn[l++]); if(r&1) ansmn = min(ansmn, mn[--r]); } int ansmx = -1; l = lold, r = rold; for(l+=sz, r+=sz; l < r; l>>=1, r>>=1){ if(l&1) ansmx = max(ansmx, mx[l++]); if(r&1) ansmx = max(ansmx, mx[--r]); } return {ansmn, ansmx}; } int greater(int v, int l, int r, int ql, int qr, int x){ if(l >= qr or r <= ql) return -1; if(mx[v] <= x) return -1; if(r-l == 1) return l; int m = (l+r)/2; int y = greater(2*v, l, m, ql, qr, x); if(y == -1) y = greater(2*v+1, m, r, ql, qr, x); return y; } int smaller(int v, int l, int r, int ql, int qr, int x){ if(l >= qr or r <= ql) return -1; if(mn[v] >= x) return -1; if(r-l == 1) return l; int m = (l+r)/2; int y = smaller(2*v, l, m, ql, qr, x); if(y == -1) y = smaller(2*v+1, m, r, ql, qr, x); return y; } }; vector<int> px, py; segment stx, sty; int h, w; void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C){ for(int i=0; i<H*W; i++) px.push_back(R[i]), py.push_back(C[i]); h = H, w = W; stx = segment(h*w, px); sty = segment(h*w, py); } int swap_seats(int a, int b){ swap(px[a], px[b]); swap(py[a], py[b]); stx.upd(a, px[a]); sty.upd(a, py[a]); stx.upd(b, px[b]); sty.upd(b, py[b]); //for(int i=0; i<h*w; i++) cout << sty.query(i, i+1).first << " " << sty.query(i, i+1).second << " " << endl; vector<int> changes; int curr = 0; while(curr != -1){ changes.push_back(curr); curr = stx.greater(1, 0, stx.sz, curr+1, h*w, px[curr]); } curr = 0; while(curr != -1){ changes.push_back(curr); curr = stx.smaller(1, 0, stx.sz, curr+1, h*w, px[curr]); } curr = 0; while(curr != -1){ changes.push_back(curr); curr = sty.greater(1, 0, sty.sz, curr+1, h*w, py[curr]); } curr = 0; while(curr != -1){ changes.push_back(curr); curr = sty.smaller(1, 0, sty.sz, curr+1, h*w, py[curr]); } sort(changes.begin(), changes.end()); int ans = 0; int prev = -2, prevpos = -1; for(int x: changes){ if(x == prevpos) continue; if(prev >= prevpos+1 and prev < x+1) ans++; auto [mnx, mxx] = stx.query(0, x+1); auto [mny, mxy] = sty.query(0, x+1); prev = (mxx-mnx+1)*(mxy-mny+1); prevpos = x; } if(prev >= prevpos+1) ans++; 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...