제출 #431856

#제출 시각아이디문제언어결과실행 시간메모리
431856Bench0310자리 배치 (IOI18_seats)C++17
25 / 100
2963 ms149736 KiB
#include <bits/stdc++.h> #include "seats.h" using namespace std; typedef long long ll; int n,h,w; vector<array<int,2>> v; vector<int> ar,br,ac,bc; int res=0; const int N=1000; set<int> row[N]; vector<int> rowmn(N,N*N); set<int> col[N]; vector<int> colmn(N,N*N); int ok(int i){return ((br[i]-ar[i]+1)*(bc[i]-ac[i]+1)==i+1);} void give_initial_chart(int nh,int nw,vector<int> r,vector<int> c) { h=nh; w=nw; n=h*w; v.assign(n,{0,0}); for(int i=0;i<n;i++) v[i]={r[i],c[i]}; ar.assign(n,v[0][0]); br.assign(n,v[0][0]); ac.assign(n,v[0][1]); bc.assign(n,v[0][1]); res=ok(0); for(int i=1;i<n;i++) { ar[i]=min(ar[i-1],v[i][0]); br[i]=max(br[i-1],v[i][0]); ac[i]=min(ac[i-1],v[i][1]); bc[i]=max(bc[i-1],v[i][1]); res+=ok(i); } for(int i=0;i<h;i++) row[i].insert(h*w); for(int i=0;i<w;i++) col[i].insert(h*w); for(int i=0;i<n;i++) { row[v[i][0]].insert(i); col[v[i][1]].insert(i); } for(int i=0;i<h;i++) rowmn[i]=(*row[i].begin()); for(int i=0;i<w;i++) colmn[i]=(*col[i].begin()); } int swap_seats(int a,int b) { if(h>1000||w>1000) { if(a>b) swap(a,b); swap(v[a],v[b]); for(int i=a;i<=b;i++) { res-=ok(i); ar[i]=min((i>0?ar[i-1]:n),v[i][0]); br[i]=max((i>0?br[i-1]:0),v[i][0]); ac[i]=min((i>0?ac[i-1]:n),v[i][1]); bc[i]=max((i>0?bc[i-1]:0),v[i][1]); res+=ok(i); } return res; } else { if(a>b) swap(a,b); row[v[a][0]].erase(a); col[v[a][1]].erase(a); row[v[b][0]].erase(b); col[v[b][1]].erase(b); swap(v[a],v[b]); row[v[a][0]].insert(a); col[v[a][1]].insert(a); row[v[b][0]].insert(b); col[v[b][1]].insert(b); rowmn[v[a][0]]=(*row[v[a][0]].begin()); rowmn[v[b][0]]=(*row[v[b][0]].begin()); colmn[v[a][1]]=(*col[v[a][1]].begin()); colmn[v[b][1]]=(*col[v[b][1]].begin()); int r=0; int now=0; // int cnt=0; // cout << "in" << endl; vector<array<int,2>> cd,ef; for(int i=0;i<h;i++) cd.push_back({rowmn[i],i}); for(int i=0;i<w;i++) ef.push_back({colmn[i],i}); sort(cd.begin(),cd.end()); sort(ef.begin(),ef.end()); int cdidx=0; int efidx=0; int c=h,d=-1,e=w,f=-1; while(now<n) { // cout << now << " "; while(cdidx<h&&cd[cdidx][0]<=now) { int t=cd[cdidx++][1]; c=min(c,t); d=max(d,t); } while(efidx<w&&ef[efidx][0]<=now) { int t=ef[efidx++][1]; e=min(e,t); f=max(f,t); } // cout << "[" << c << "," << d << "," << e << "," << f << "] "; // cout.flush(); if((d-c+1)*(f-e+1)==now+1) r++; now=max(now+1,(d-c+1)*(f-e+1)-1); // cnt++; } // assert(cnt<=2*(w+h)); // cout << endl; return r; } } //int main() //{ // // 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...