Submission #132876

#	Time	Username	Problem	Language	Result	Execution time	Memory
132876		amiratou	Seats (IOI18_seats)	C++14	11 / 100	4049 ms	64632 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define ii pair<int,int>
#define INF (int)(1e9)
pair<ii,ii> tab[1000002];
int A[1000002],n,A_x[1000002],A_y[1000002],h,w;
ii st_x[4000005],st_y[4000005];
vector<int> r,c;
int ones=0,zeros=0;
void build(int node,int l,int r){
	if(l==r){
		st_x[node]=ii(A_x[l],A_x[l]);
		st_y[node]=ii(A_y[l],A_y[l]);
		return ;
	}
	int med=(l+r)/2;
	build(node*2,l,med),build(node*2+1,med+1,r);
	st_x[node].fi=max(st_x[node*2].fi,st_x[node*2+1].fi);
	st_x[node].se=min(st_x[node*2].se,st_x[node*2+1].se);
	st_y[node].fi=max(st_y[node*2].fi,st_y[node*2+1].fi);
	st_y[node].se=min(st_y[node*2].se,st_y[node*2+1].se);
}
ii query_x(int node,int l,int r,int i,int j){
	if(l>j||r<i)
		return ii(-1,INF);
	if(l>=i&&r<=j)
		return st_x[node];
	int med=(l+r)/2;
	ii q1=query_x(node*2,l,med,i,j),q2=query_x(node*2+1,med+1,r,i,j);
	return ii(max(q1.fi,q2.fi),min(q1.se,q2.se));
}
ii query_y(int node,int l,int r,int i,int j){
	if(l>j||r<i)
		return ii(-1,INF);
	if(l>=i&&r<=j)
		return st_y[node];
	int med=(l+r)/2;
	ii q1=query_y(node*2,l,med,i,j),q2=query_y(node*2+1,med+1,r,i,j);
	return ii(max(q1.fi,q2.fi),min(q1.se,q2.se));
}
void update(int node,int l,int r,int idx,int x,int y){
	if(r<idx||l>idx)
		return ;
	if(l==r){
		st_x[node]=ii(x,x);
		st_y[node]=ii(y,y);
		return ;
	}
	int med=(l+r)/2;
	update(node*2,l,med,idx,x,y),update(node*2+1,med+1,r,idx,x,y);
	st_x[node].fi=max(st_x[node*2].fi,st_x[node*2+1].fi);
	st_x[node].se=min(st_x[node*2].se,st_x[node*2+1].se);
	st_y[node].fi=max(st_y[node*2].fi,st_y[node*2+1].fi);
	st_y[node].se=min(st_y[node*2].se,st_y[node*2+1].se);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	n=H*W,h=H,w=W;
	r=R,c=C;
	if(H<=1000&&W<=1000){
		for (int i = 0; i < n; ++i)
			A_x[i]=R[i],A_y[i]=C[i];
		build(1,0,n-1);
		return;
	}
	for (int i = 0; i < n; ++i)
	{
		tab[i].fi=ii(R[i],C[i]);
		tab[i].se=ii(R[i],C[i]);
		if(i){
			tab[i].fi.fi=max(tab[i].fi.fi,tab[i-1].fi.fi);
			tab[i].fi.se=max(tab[i].fi.se,tab[i-1].fi.se);
			tab[i].se.fi=min(tab[i].se.fi,tab[i-1].se.fi);
			tab[i].se.se=min(tab[i].se.se,tab[i-1].se.se);
		}
		if((tab[i].fi.fi-tab[i].se.fi+1)*(tab[i].fi.se-tab[i].se.se+1)==(i+1))A[i]=1,ones++;
		else A[i]=0,zeros++;
	}
}

int swap_seats(int a, int b) {
	if(h<=1000&&w<=1000){
		swap(A_x[a],A_x[b]),swap(A_y[a],A_y[b]);
		update(1,0,n-1,a,A_x[a],A_y[a]),update(1,0,n-1,b,A_x[b],A_y[b]);
		int last=0,ans=0;
		ii X=ii(0,INF),Y=ii(0,INF);
		for (int i = 0; i < n;)
		{
			ii q1=query_x(1,0,n-1,last,i),q2=query_y(1,0,n-1,last,i);
			X.fi=max(X.fi,q1.fi),X.se=min(X.se,q1.se),Y.fi=max(Y.fi,q2.fi),Y.se=min(Y.se,q2.se);
			if((X.fi-X.se+1)*(Y.fi-Y.se+1)==(i+1))
				ans++;
			if((X.fi-X.se+1)*(Y.fi-Y.se+1)>i+1)
				i=(X.fi-X.se+1)*(Y.fi-Y.se+1)-1;
			else i++;
		}
		return ans;

	}
	swap(r[a],r[b]),swap(c[a],c[b]);
	for (int i = min(a,b); i <= max(a,b); ++i)
	{
		tab[i].fi=ii(r[i],c[i]);
		tab[i].se=ii(r[i],c[i]);
		if(i){
			tab[i].fi.fi=max(tab[i].fi.fi,tab[i-1].fi.fi);
			tab[i].fi.se=max(tab[i].fi.se,tab[i-1].fi.se);
			tab[i].se.fi=min(tab[i].se.fi,tab[i-1].se.fi);
			tab[i].se.se=min(tab[i].se.se,tab[i-1].se.se);
		}
		if((tab[i].fi.fi-tab[i].se.fi+1)*(tab[i].fi.se-tab[i].se.se+1)==(i+1)){
			if(!A[i])
				A[i]=1,ones++,zeros--;
		}
		else {
			if(A[i])
				A[i]=0,ones--,zeros++;
		}
	}
	return ones;
}

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