| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 371539 | denkendoemeer | Seats (IOI18_seats) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "seats.h"
#define ll long long
using namespace std;
int lazy[1<<21],b[1000005],h,w;
vector<int>r,c;
vector<vector<int>>auxi;
array<int,2>aint[1<<21];
void comb(int nod)
{
aint[nod]={min(aint[nod*2][0],aint[nod*2+1][0])};
aint[nod][1]=0;
if (aint[nod*2][0]>aint[nod][0])
aint[nod][1]+=0;
else
aint[nod][1]+=aint[nod*2][1];
if (aint[nod*2+1][0]>aint[nod][0])
aint[nod][1]+=0;
else
aint[nod][1]+=aint[nod*2+1][1];
}
void build(int nod=1,int st=0,int dr=h*w-1)
{
if (st==dr){
aint[nod]={b[st],1};
return ;
}
int mij=(st+dr)/2;
build(nod*2,st,mij);
build(nod*2+1,mij+1,dr);
comb(nod);
}
void add(int nod,int x)
{
aint[nod][0]+=x;
lazy[nod]+=x;
}
void update(int st,int dr,int val,int nod=1,int l=0,int r=h*w-1)
{
if (aint[1][1]==0){
b[st]+=val;
b[dr+1]-=val;
return ;
}
if (st<=l && r<=dr){
add(nod,val);
return ;
}
int mij=(l+r)/2;
add(2*nod,lazy[nod]);
add(2*nod+1,lazy[nod]);
lazy[nod]=0;
if (st<=mij)
update(st,dr,val,2*i,l,mij);
if (mij+1<=dr)
update(st,dr,val,2*i+1,mij+1,r);
comb(nod);
}
void swa(int x,int y,int z)
{
vector<int>v;
int i,j;
for(i=!x-1;i<(x<h);i++)
for(j=!y-1;j<(y<w);j++)
v.push_back(auxi[x+i][y+j]);
sort(v.begin(),v.end());
update(v[0],(v.size()>1?v[1]:h*w)-1,z);
if (v.size()>2)
update(v[2],v[3]-1,z);
}
void give_initial_chart(int h2,int w2,vector<int>r2,vector<int>c2)
{
h=h2;
w=w2;
r=r2;
c=c2;
auxi=vector<vector<int>>(h,vector<int>(w));
int i;
for(i=0;i<h*w;i++)
auxi[r[i]][c[i]]=i;
for(i=0;i<=h;i++)
for(j=0;j<=w;J++)
swa(i,j,1);
for(i=0;i<h*w;i++)
b[i+1]+=b[i];
build();
}
int swap_seats(int x,int y)
{
int i,j,k;
vector<array<int,2>>v;
for(i:{x,y})
for(j:{0,1})
for(k:{0,1})
v.push_back({r[i]+j,c[i]+k});
sort(v.begin(),v.end());
v.resize(unique(v.begin(),v.end())-v.begin());
for(auto it:v)
swa(it[0],it[1],-1);
swap(auxi[r[x]][c[x]],auxi[r[y]][c[y]]);
swap(r[x],r[y]);
swap(c[x],c[y]);
for(auto it:v)
swa(it[0],it[1],1);
return aint[1][1];
}