Submission #554481

#	Time	Username	Problem	Language	Result	Execution time	Memory
554481		jamezzz	Seats (IOI18_seats)	C++17	100 / 100	2769 ms	119340 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

#define pf printf
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;

#define maxn 4000005

int h,w,n;
vector<int> r,c;
vector<vector<int>> a;

int lz[maxn];
ii v[maxn];//{min element,#min}

void init(int i,int s,int e){
	v[i]={0,e-s+1};
	if(s!=e){
		int m=(s+e)>>1;
		init(2*i+1,s,m);
		init(2*i+2,m+1,e);
	}
}

void ppo(int i,int s,int e){
	v[i].fi+=lz[i];
	if(s!=e){
		int m=(s+e)>>1;
		lz[2*i+1]+=lz[i];
		lz[2*i+2]+=lz[i];
	}
	lz[i]=0;
}

void up(int i,int s,int e,int x,int y,int nv){
	if(s==x&&e==y){lz[i]+=nv;return;}
	int m=(s+e)>>1;
	if(y<=m)up(2*i+1,s,m,x,y,nv);
	else if(x>m)up(2*i+2,m+1,e,x,y,nv);
	else up(2*i+1,s,m,x,m,nv),up(2*i+2,m+1,e,m+1,y,nv);
	ppo(2*i+1,s,m);ppo(2*i+2,m+1,e);
	if(v[2*i+1].fi==v[2*i+2].fi)v[i]={v[2*i+1].fi,v[2*i+1].se+v[2*i+2].se};
	else v[i]=min(v[2*i+1],v[2*i+2]);
}

inline void up(int x,int y,int nv){
	if(x>y)return;
	up(0,0,n-1,x,y,nv);
}

inline int qry(){
	if(v[0].fi+lz[0]==4)return v[0].se;
	return 0;
}

inline void upd(int r,int c,int m){//update 2x2 with (r,c) as top left
	vector<int> v={a[r][c],a[r][c+1],a[r+1][c],a[r+1][c+1]};
	sort(all(v));
	up(v[0],v[1]-1,m*1);//3 white 1 black, +-1
	up(v[2],v[3]-1,m*5);//3 black 1 white, +-inf(=5 since max is 4)
}

inline void upd2(int r,int c,int m){//update all squares containing (r,c)
	upd(r,c,m);
	upd(r-1,c,m);
	upd(r,c-1,m);
	upd(r-1,c-1,m);
}

void give_initial_chart(int H,int W,vector<int> R,vector<int> C){
	h=H;w=W;n=h*w;
	for(int i:R)r.pb(i+1);
	for(int i:C)c.pb(i+1);
	a.resize(h+2);
	for(int i=0;i<h+2;++i){
		a[i].resize(w+2,h*w);
	}
	for(int i=0;i<h*w;++i){
		a[r[i]][c[i]]=i;
	}
	init(0,0,n-1);
	for(int i=0;i<=h;++i){
		for(int j=0;j<=w;++j){
			upd(i,j,1);
		}
	}
}

int swap_seats(int x,int y){
	upd2(r[x],c[x],-1);
	upd2(r[y],c[y],-1);
	
	swap(a[r[x]][c[x]],a[r[y]][c[y]]);
	swap(r[x],r[y]);
	swap(c[x],c[y]);
	
	upd2(r[x],c[x],1);
	upd2(r[y],c[y],1);
	return qry();
}

Compilation message (stderr)

seats.cpp: In function 'void ppo(int, int, int)':
seats.cpp:33:7: warning: unused variable 'm' [-Wunused-variable]
   33 |   int m=(s+e)>>1;
      |       ^

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 20 / 20
• Subtask 4: 6 / 6
• Subtask 5: 33 / 33
• Subtask 6: 30 / 30