제출 #827492

#제출 시각아이디문제언어결과실행 시간메모리
827492I_Love_EliskaM_자리 배치 (IOI18_seats)C++17
100 / 100
2618 ms84960 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; #define forn(i,n) for(int i=0;i<n;++i) #define pb push_back #define all(x) x.begin(), x.end() #define set(x,a,b,c,d) x[0]=a,x[1]=b,x[2]=c,x[3]=d; const int inf = 1e9; const int sz = 1<<20; struct node { int mn=inf, cnt=0; node(int a, int b) {mn=a,cnt=b;} node() {} }; node t[2*sz]; int lazy[4*sz]; void build(int v, int l, int r) { if (r-l==1) return; int m=(l+r)>>1; build(2*v+1,l,m); build(2*v+2,m,r); if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt}; else if (t[2*v+1].mn < t[2*v+2].mn) t[v]=t[2*v+1]; else t[v]=t[2*v+2]; } void init(int n, int m) { forn(i,n*m) t[sz-1+i]={0,1}; build(0,0,sz); } void add(int v, int l, int r, int lx, int rx, int x) { if (lazy[v]) { t[v].mn+=lazy[v]; lazy[2*v+1]+=lazy[v]; lazy[2*v+2]+=lazy[v]; lazy[v]=0; } if (rx<=l || r<=lx) return; if (lx<=l && r<=rx) { t[v].mn+=x; lazy[2*v+1]+=x; lazy[2*v+2]+=x; return; } int m=(l+r)>>1; add(2*v+1,l,m,lx,rx,x); add(2*v+2,m,r,lx,rx,x); if (t[2*v+1].mn==t[2*v+2].mn) t[v] = {t[2*v+1].mn, t[2*v+1].cnt+t[2*v+2].cnt}; else if (t[2*v+1].mn < t[2*v+2].mn) t[v]=t[2*v+1]; else t[v]=t[2*v+2]; } void add(int l, int r, int x) { if (l>=r) return; add(0,0,sz,l,r,x); } int R[sz], C[sz]; int swapped=0; int n,m; vector<vector<int>> a; int z[4]; void give_initial_chart(int _n, int _m, vector<int> _r, vector<int> _c) { n=_n, m=_m; if (n==1 && m==1) return; forn(i,n*m) R[i]=_r[i]+1, C[i]=_c[i]+1; if (m==1) { swap(n,m); forn(i,n*m) swap(R[i],C[i]); swapped=1; } init(n,m); a.assign(n+2,vector<int>(m+2,n*m)); forn(i,n*m) a[R[i]][C[i]]=i; for (int i=0; i<=n; ++i) { for (int j=0; j<=m; ++j) { set(z,a[i][j],a[i+1][j],a[i][j+1],a[i+1][j+1]); sort(z,z+4); add(z[0],z[1],1); add(z[2],z[3],1); } } } int swap_seats(int x, int y) { if (n==1 && m==1) return 1; int p=R[x], q=C[x], u=R[y], v=C[y]; set(z,a[p][q],a[p][q+1],a[p+1][q],a[p+1][q+1]); sort(z,z+4); add(z[0],z[1],-1); add(z[2],z[3],-1); set(z,a[p][q],a[p][q+1],a[p-1][q],a[p-1][q+1]); sort(z,z+4); add(z[0],z[1],-1); add(z[2],z[3],-1); set(z,a[p][q],a[p][q-1],a[p+1][q],a[p+1][q-1]); sort(z,z+4); add(z[0],z[1],-1); add(z[2],z[3],-1); set(z,a[p][q],a[p][q-1],a[p-1][q],a[p-1][q-1]); sort(z,z+4); add(z[0],z[1],-1); add(z[2],z[3],-1); p=u, q=v; set(z,a[p][q],a[p][q+1],a[p+1][q],a[p+1][q+1]); sort(z,z+4); add(z[0],z[1],-1); add(z[2],z[3],-1); set(z,a[p][q],a[p][q+1],a[p-1][q],a[p-1][q+1]); sort(z,z+4); add(z[0],z[1],-1); add(z[2],z[3],-1); set(z,a[p][q],a[p][q-1],a[p+1][q],a[p+1][q-1]); sort(z,z+4); add(z[0],z[1],-1); add(z[2],z[3],-1); set(z,a[p][q],a[p][q-1],a[p-1][q],a[p-1][q-1]); sort(z,z+4); add(z[0],z[1],-1); add(z[2],z[3],-1); swap(R[x],R[y]); swap(C[x],C[y]); a[R[x]][C[x]]=x; a[R[y]][C[y]]=y; p=R[x], q=C[x], u=R[y], v=C[y]; set(z,a[p][q],a[p][q+1],a[p+1][q],a[p+1][q+1]); sort(z,z+4); add(z[0],z[1],1); add(z[2],z[3],1); set(z,a[p][q],a[p][q+1],a[p-1][q],a[p-1][q+1]); sort(z,z+4); add(z[0],z[1],1); add(z[2],z[3],1); set(z,a[p][q],a[p][q-1],a[p+1][q],a[p+1][q-1]); sort(z,z+4); add(z[0],z[1],1); add(z[2],z[3],1); set(z,a[p][q],a[p][q-1],a[p-1][q],a[p-1][q-1]); sort(z,z+4); add(z[0],z[1],1); add(z[2],z[3],1); p=u, q=v; set(z,a[p][q],a[p][q+1],a[p+1][q],a[p+1][q+1]); sort(z,z+4); add(z[0],z[1],1); add(z[2],z[3],1); set(z,a[p][q],a[p][q+1],a[p-1][q],a[p-1][q+1]); sort(z,z+4); add(z[0],z[1],1); add(z[2],z[3],1); set(z,a[p][q],a[p][q-1],a[p+1][q],a[p+1][q-1]); sort(z,z+4); add(z[0],z[1],1); add(z[2],z[3],1); set(z,a[p][q],a[p][q-1],a[p-1][q],a[p-1][q-1]); sort(z,z+4); add(z[0],z[1],1); add(z[2],z[3],1); return t[0].cnt; }
#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...