제출 #138873

#제출 시각아이디문제언어결과실행 시간메모리
138873Nnandi자리 배치 (IOI18_seats)C++14
17 / 100
4112 ms188764 KiB
#include<bits/stdc++.h> #include "seats.h" using namespace std; const int maxn = 1000005; const int INF = INT_MAX - 1; int jo[maxn]; struct Elem { int h_max, h_min; int w_max, w_min; bool ures; Elem() { ures = true; h_max = -1; h_min = INF; w_max = -1; w_min = INF; } Elem(int x, int y) { ures = false; h_max = x; h_min = x; w_max = y; w_min = y; } void rep(Elem a, Elem b) { ures = a.ures && b.ures; h_max = max(a.h_max,b.h_max); h_min = min(a.h_min,b.h_min); w_max = max(a.w_max,b.w_max); w_min = min(a.w_min,b.w_min); } int get_size() { if(ures) return 0; return (h_max - h_min + 1) * (w_max - w_min + 1); } }; Elem fa[maxn*8]; void epit(int hol, int tol, int ig, vector<int> &R, vector<int> &C) { if(tol == ig) { fa[hol] = Elem(R[tol],C[tol]); return; } int mid = (tol + ig) / 2; epit(hol*2,tol,mid,R,C); epit(hol*2+1,mid+1,ig,R,C); fa[hol].rep(fa[hol*2],fa[hol*2+1]); return; } Elem ask(int hol, int tol, int ig, int to) { if(ig <= to) { return fa[hol]; } Elem uj; if(to < tol) { return uj; } int mid = (tol + ig) / 2; uj.rep(ask(hol*2,tol,mid,to),ask(hol*2+1,mid+1,ig,to)); return uj; } void modif(int hol, int tol, int ig, int poz, Elem &val) { if(tol == ig) { fa[hol] = val; return; } int mid = (tol + ig) / 2; if(poz <= mid) { modif(hol*2,tol,mid,poz,val); } else { modif(hol*2+1,mid+1,ig,poz,val); } fa[hol].rep(fa[hol*2],fa[hol*2+1]); return; } int szep = 0; vector<int> R, C; int N; void give_initial_chart(int H, int W, vector<int> RR, vector<int> CC) { R = RR; C = CC; N = H * W; epit(1,0,N-1,R,C); for(int i=0;i<N;i++) { if(ask(1,0,N-1,i).get_size() == i+1) { szep++; jo[i] = 1; } } return; } int swap_seats(int a, int b) { swap(R[a],R[b]); swap(C[a],C[b]); Elem A(R[a],C[a]); Elem B(R[b],C[b]); modif(1,0,N-1,a,A); modif(1,0,N-1,b,B); Elem r = ask(1,0,N-1,min(a,b)); for(int i=min(a,b);i<max(a,b);i++) { szep -= jo[i]; jo[i] = 0; if(r.get_size() == i+1) { jo[i] = 1; } szep += jo[i]; Elem U(R[i+1],C[i+1]); r.rep(r,U); } return szep; }
#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...