Submission #1093464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093464		StefanSebez	Seats (IOI18_seats)	C++14	100 / 100	3084 ms	117696 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,X[N+50],Y[N+50];
vector<int>A[N+50];
struct Node{int mn,num;}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};
}
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]]);
}
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};
	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]);
	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);
}
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;
	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;
	node[0]={inf,0};
	for(int i=1;i<=n*m;i++) {Sredi(X[i],Y[i],1);}
}
int swap_seats(int a, int b) {
	a++,b++;
	UPDATE(a,-1);
	UPDATE(b,-1);
	swap(A[X[a]][Y[a]],A[X[b]][Y[b]]),swap(X[a],X[b]),swap(Y[a],Y[b]);
	UPDATE(a,1);
	UPDATE(b,1);
	return node[root].num;
}

Compilation message (stderr)

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