Submission #827467

#TimeUsernameProblemLanguageResultExecution timeMemory
827467I_Love_EliskaM_Seats (IOI18_seats)C++17
100 / 100
2688 ms83804 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() 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 merge(int v) { 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 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); merge(v); } void init(int n, int m) { forn(i,n*m) t[sz-1+i]={0,1}; build(0,0,sz); } void push(int v) { t[v].mn+=lazy[v]; lazy[2*v+1]+=lazy[v]; lazy[2*v+2]+=lazy[v]; lazy[v]=0; } void add(int v, int l, int r, int lx, int rx, int x) { if (lazy[v]) push(v); if (rx<=l || r<=lx) return; if (lx<=l && r<=rx) { lazy[v]+=x; push(v); return; } int m=(l+r)>>1; if (m>lx) add(2*v+1,l,m,lx,rx,x); else if (lazy[2*v+1]) push(2*v+1); if (m<rx) add(2*v+2,m,r,lx,rx,x); else if (lazy[2*v+2]) push(2*v+2); merge(v); } 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 v[4]; void check(int i, int j, int x) { v[0] = a[i][j]; v[1] = a[i][j+1]; v[2] = a[i+1][j]; v[3] = a[i+1][j+1]; sort(v, v+4); add(v[0],v[1],x); add(v[2],v[3],x); } 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) { check(i,j,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]; vector<int> z; check(p,q,-1); check(p-1,q-1,-1); check(p-1,q,-1); check(p,q-1,-1); p=u, q=v; check(p,q,-1); check(p-1,q-1,-1); check(p-1,q,-1); check(p,q-1,-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]; check(p,q,1); check(p-1,q-1,1); check(p-1,q,1); check(p,q-1,1); p=u, q=v; check(p,q,1); check(p-1,q-1,1); check(p-1,q,1); check(p,q-1,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...