Submission #1093463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093463		StefanSebez	Seats (IOI18_seats)	C++14	100 / 100	3170 ms	133744 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e6+50,inf=1e9;
int n,m,res;
int X[N+50],Y[N+50],L[N+50],R[N+50],LL[N+50],RR[N+50];
vector<int>A[N+50];
/*struct Node{
	int L,R,LL,RR;
}node[2*N];
Node Merge(Node a,Node b){return {min(a.L,b.L),max(a.R,b.R),min(a.LL,b.LL),max(a.RR,b.RR)};}
int nc,root,lc[2*N],rc[2*N];
void Update(int &c,int ss,int se,int qind,Node qval){
	if(!c){c=++nc;}
	if(ss==se){node[c]=qval;return;}
	int mid=ss+se>>1;
	if(qind<=mid) Update(lc[c],ss,mid,qind,qval);
	else Update(rc[c],mid+1,se,qind,qval);
	node[c]=Merge(node[lc[c]],node[rc[c]]);
}
Node Get(int &c,int ss,int se,int qs,int qe){
	if(qs<=ss && se<=qe) return node[c];
	if(qe<ss || se<qs) return {inf,0,inf,0};
	int mid=ss+se>>1;
	return Merge(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
}*/
struct Node{
	int mn,num;
	//Node(){}
	//Node(int a,int b){mn[0]=mn[1]=mn[2]=mn[3]=a,num[0]=num[1]=num[2]=num[3]=b;}
	//Node(int a0,int a1,int a2,int a3,int b0,int b1,int b2,int b3){mn[0]=a0,mn[1]=a1,mn[2]=a2,mn[3]=a3,num[0]=b0,num[1]=b1,num[2]=b2,num[3]=b3;}
}node[2*N];
Node Merge(Node a,Node b){
	if(a.mn<b.mn) return a;
	if(a.mn>b.mn)return b;
	return {a.mn,a.num+b.num};
	/*Node C=Node(inf,0);
	bool bul0=true,bul1=true;
	for(int i=0;i<3;i++) {if(a.mn[i]!=a.mn[i+1]) bul0=false;if(b.mn[i]!=b.mn[i+1]) bul1=false;}
	if(!bul1) return a;
	if(!bul0) return b;
	if(a.mn[0]<b.mn[0]) return a;
	if(a.mn[0]>b.mn[0]) return b;
	C=Node(a.mn[0],0);
	C.num[0]=a.num[0]+b.num[0];*/
	/*for(int i=0;i<=3;i++){
		if(a.mn[i]<b.mn[i]) C.mn[i]=a.mn[i],C.num[i]=a.num[i];
		else if(a.mn[i]>b.mn[i]) C.mn[i]=b.mn[i],C.num[i]=b.num[i];
		else C.mn[i]=a.mn[i],C.num[i]=a.num[i]+b.num[i];
	}*/
	/*bool bul=true;
	for(int i=0;i<=3;i++) if(a.mn[i]<b.mn[i]) bul=false;
	if(bul) swap(a,b);
	for(int i=0;i<=3;i++){
		C.mn[i]=a.mn[i];C.num[i]=a.num[i];
		if(a.num[i]==b.num[i]){C.num[i]+=b.num[i];}
	}*/
	//return C;
}
int root,nc,lc[2*N],rc[2*N],lazy[2*N];
void update(int &c,int ss,int se,int qval){
	if(!c){c=++nc;node[c]={0,se-ss+1};}
	node[c].mn+=qval;
	lazy[c]+=qval;
}
void push(int &c,int ss,int se){
	int mid=ss+se>>1;
	update(lc[c],ss,mid,lazy[c]);
	update(rc[c],mid+1,se,lazy[c]);
	lazy[c]=0;
}
void Update(int &c,int ss,int se,int qs,int qe,int qval){
	if(qs>qe) return;
	if(!c){c=++nc;node[c]={0,se-ss+1};}
	if(qs<=ss && se<=qe){update(c,ss,se,qval);return;}
	if(qe<ss || se<qs) return;
	int mid=ss+se>>1;
	push(c,ss,se);
	Update(lc[c],ss,mid,qs,qe,qval),Update(rc[c],mid+1,se,qs,qe,qval);
	node[c]=Merge(node[lc[c]],node[rc[c]]);
	//printf("%i %i: %i %i\n",ss,se,node[c].mn,node[c].num);
}
Node Get(int &c,int ss,int se,int qs,int qe){
	//if(qs!=qe)printf("%i %i: %i %i\n",ss,se,node[c].mn,node[c].num);
	if(qs<=ss && se<=qe) return node[c];
	if(qe<ss || se<qs) return {inf,0};
	int mid=ss+se>>1;
	push(c,ss,se);
	return Merge(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
}
void Update2x2(int x,int y,int x0,int y0,int qval){
	if(x<=0 || x>n+1 || y<=0 || y>m+1) return;
	int J=inf;
	for(int i=0;i>=-1;i--) for(int j=0;j>=-1;j--) if(!(x+i==x0 && y+j==y0)) J=min(J,A[x+i][y+j]);
	//printf("*%i %i %i %i %i %i\n",x,y,x0,y0,A[x0][y0],J-1);
	Update(root,1,n*m,A[x0][y0],J-1,qval);
	J=-inf;
	for(int i=0;i>=-1;i--) for(int j=0;j>=-1;j--) if(!(x+i==x0 && y+j==y0)) J=max(J,A[x+i][y+j]);
	Update(root,1,n*m,J,A[x0][y0]-1,qval);
}
void Updateceo(int x,int y,int qval){
	Update2x2(x,y,x,y,qval);
	Update2x2(x,y,x-1,y,qval);
	Update2x2(x,y,x,y-1,qval);
	Update2x2(x,y,x-1,y-1,qval);
}
void Sredi(int x,int y,int qval){
	Update2x2(x,y,x,y,qval);
	Update2x2(x+1,y,x,y,qval);
	Update2x2(x,y+1,x,y,qval);
	Update2x2(x+1,y+1,x,y,qval);
	/*int j;
	//printf("%i: %i\n",i,j);
	j=min({A[x-1][y],A[x-1][y-1],A[x][y-1]})-1;
	Update(root,1,n*m,i,j,qval);
	j=min({A[x-1][y],A[x-1][y-1],A[x][y-1]})+1;
	Update(root,1,n*m,j,i,qval);
	//for(int i=0;i<=3;i++) printf("(%i,%i) ",node[root].mn[i],node[root].num[i]);printf("\n");
	j=min({A[x+1][y],A[x+1][y-1],A[x][y-1]})-1;
	Update(root,1,n*m,i,j,qval);
	j=min({A[x+1][y],A[x+1][y-1],A[x][y-1]})+1;
	Update(root,1,n*m,j,i,qval);
	//for(int i=0;i<=3;i++) printf("(%i,%i) ",node[root].mn[i],node[root].num[i]);printf("\n");
	j=min({A[x-1][y],A[x-1][y+1],A[x][y+1]})-1;
	Update(root,1,n*m,i,j,qval);
	j=min({A[x-1][y],A[x-1][y+1],A[x][y+1]})+1;
	Update(root,1,n*m,j,i,qval);
	//for(int i=0;i<=3;i++) printf("(%i,%i) ",node[root].mn[i],node[root].num[i]);printf("\n");
	j=min({A[x+1][y],A[x+1][y+1],A[x][y+1]})-1;
	Update(root,1,n*m,i,j,qval);
	j=min({A[x+1][y],A[x+1][y+1],A[x][y+1]})+1;
	Update(root,1,n*m,j,i,qval);
	//for(int i=0;i<=3;i++) printf("(%i,%i) ",node[root].mn[i],node[root].num[i]);printf("\n");*/
}
void UPDATE(int a,int qval){
	int x=X[a],y=Y[a];
	Updateceo(x,y,qval);
	Updateceo(x+1,y,qval);
	Updateceo(x,y+1,qval);
	Updateceo(x+1,y+1,qval);
}
void give_initial_chart(int H, int W, std::vector<int> r, std::vector<int> c) {
	n=H,m=W;
	for(int i=1;i<=n*m;i++) X[i]=r[i-1]+1,Y[i]=c[i-1]+1;
	/*L[0]=LL[0]=inf;
	for(int i=1;i<=n*m;i++){
		L[i]=min(L[i-1],X[i]),R[i]=max(R[i-1],X[i]);
		LL[i]=min(LL[i-1],Y[i]),RR[i]=max(RR[i-1],Y[i]);
		if((R[i]-L[i]+1)*(RR[i]-LL[i]+1)==i) res++;
	}*/
	node[0]={inf,0};
	for(int i=0;i<=n+1;i++) for(int j=0;j<=m+1;j++) A[i].pb(n*m+1);
	for(int i=1;i<=n*m;i++) A[X[i]][Y[i]]=i;
	//for(int i=0;i<=n+1;i++) {for(int j=0;j<=m+1;j++) printf("%i ",A[i][j]);printf("\n");}
	for(int i=1;i<=n*m;i++) {Sredi(X[i],Y[i],1);}
	//for(int i=1;i<=n*m;i++) printf("%i ",Get(root,1,n*m,i,i).mn);printf("\n");
	//printf("%i\n",Get(root,1,n*m,2,4).num);
	//printf("%i %i\n",node[root].mn,node[root].num);
	//for(int i=1;i<=n*m;i++) printf("{%i,%i} ",Get(root,1,n*m,i,i).mn[3],Get(root,1,n*m,i,i).num[0]);printf("\n");
}

int swap_seats(int a, int b) {
	a++,b++;
	if(a>b) swap(a,b);
	UPDATE(a,-1);
	UPDATE(b,-1);
	//for(int i=1;i<=n*m;i++) printf("%i ",Get(root,1,n*m,i,i).mn);printf("\n");
	swap(A[X[a]][Y[a]],A[X[b]][Y[b]]),swap(X[a],X[b]),swap(Y[a],Y[b]);
	//for(int i=0;i<=n+1;i++) {for(int j=0;j<=m+1;j++) printf("%i ",A[i][j]);printf("\n");}
	UPDATE(a,1);
	UPDATE(b,1);
	//for(int i=1;i<=n*m;i++) printf("%i ",Get(root,1,n*m,i,i).mn);printf("\n");
	Node ans=node[root];
	return ans.num;
	/*if(n<=1000 && m<=1000){
		Update(root,1,n*m,b,{X[a],X[a],Y[a],Y[a]});
		Update(root,1,n*m,a,{X[b],X[b],Y[b],Y[b]});
		swap(X[a],X[b]),swap(Y[a],Y[b]);
		int i=1,ans=0;
		Node x={inf,0,inf,0};
		while(i<=n*m){
			x=Merge(x,{X[i],X[i],Y[i],Y[i]});
			int d=(x.R-x.L+1)*(x.RR-x.LL+1)-i;
			if(d==0) ans++,d=1;
			x=Merge(x,Get(root,1,n*m,i,i+d));
			i+=d;
		}
		return ans;
	}
	else{
		swap(X[a],X[b]),swap(Y[a],Y[b]);
		for(int i=a;i<=b;i++) if((R[i]-L[i]+1)*(RR[i]-LL[i]+1)==i) res--;
		for(int i=a;i<=b;i++){
			L[i]=min(L[i-1],X[i]),R[i]=max(R[i-1],X[i]);
			LL[i]=min(LL[i-1],Y[i]),RR[i]=max(RR[i-1],Y[i]);
			if((R[i]-L[i]+1)*(RR[i]-LL[i]+1)==i) res++;
		}
		return res;
	}*/
}

Compilation message (stderr)

seats.cpp: In function 'void push(int&, int, int)':
seats.cpp:72:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |  int mid=ss+se>>1;
      |            ^
seats.cpp: In function 'void Update(int&, int, int, int, int, int)':
seats.cpp:82:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |  int mid=ss+se>>1;
      |            ^
seats.cpp: In function 'Node Get(int&, int, int, int, int)':
seats.cpp:92:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |  int mid=ss+se>>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