Submission #1090644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090644		StefanSebez	Seats (IOI18_seats)	C++14	37 / 100	4022 ms	103508 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];
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));
}
void give_initial_chart(int H, int W, std::vector<int> r, std::vector<int> c) {
	node[0]={inf,0,inf,0};
	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=1;i<=n*m;i++) Update(root,1,n*m,i,{X[i],X[i],Y[i],Y[i]});
	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++;
	}
}

int swap_seats(int a, int b) {
	a++,b++;
	if(a>b) swap(a,b);
	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 Update(int&, int, int, int, Node)':
seats.cpp:20:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |  int mid=ss+se>>1;
      |            ^
seats.cpp: In function 'Node Get(int&, int, int, int, int)':
seats.cpp:28:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |  int mid=ss+se>>1;
      |            ^

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