Submission #420406

#	Time	Username	Problem	Language	Result	Execution time	Memory
420406		Jasiekstrz	Seats (IOI18_seats)	C++17	37 / 100	4026 ms	69596 KiB

seats

#include<bits/stdc++.h>
#include "seats.h"
#define fi first
#define se second
using namespace std;
const int N=1e6;
const int P=11e5;
int ans=0;
pair<int,int> tab[N+10];
int w[N+10][4];
struct T
{
	int a,b,c,d;
	T operator+(const T &oth)
	{
		return {min(a,oth.a),max(b,oth.b),min(c,oth.c),max(d,oth.d)};
	}
	bool operator==(const T &oth)
	{
		return (a==oth.a && b==oth.b && c==oth.c && d==oth.d);
	}
	bool operator!=(const T &oth)
	{
		return (a!=oth.a || b!=oth.b || c!=oth.c || d!=oth.d);
	}
};
bool hw=false;
int h,wi;
int pot;
T tree[2*P+10];
void upd_t(int x,pair<int,int> c)
{
	x+=pot-1;
	tree[x]={c.fi,c.fi,c.se,c.se};
	for(x/=2;x>0;x/=2)
		tree[x]=tree[2*x]+tree[2*x+1];
	return;
}
T read_t(int r)
{
	int l=pot;
	r+=pot-1;
	T ww={h,0,wi,0};
	for(;l<=r;l/=2,r/=2)
	{
		if(l%2==1)
			ww=ww+tree[l++];
		if(r%2==0)
			ww=ww+tree[r--];
	}
	return ww;
}
int bs_t(int x,T d)
{
	x+=pot-1;
	while(d+tree[x]==d)
	{
		if(x%2==0)
			x/=2;
		else
		{
			x++;
			x/=2;
		}
	}
	while(x<pot)
	{
		if(d+tree[2*x]!=d)
			x=2*x;
		else
			x=2*x+1;
	}
	return x-pot+1;
}
void solvehw(int H,int W,vector<int> R,vector<int> C)
{
	h=H;
	wi=W;
	for(pot=1;pot<h*wi;pot*=2);
	for(int i=1;i<=h*wi;i++)
		tree[pot+i-1]={R[i-1],R[i-1],C[i-1],C[i-1]};
	for(int i=pot-1;i>0;i--)
		tree[i]=tree[2*i]+tree[2*i+1];
	return;
}
int swaphw(int a,int b)
{
	upd_t(a,tab[b]);
	upd_t(b,tab[a]);
	swap(tab[a],tab[b]);
	int ww=1;
	int lst=1;
	T d={tab[1].fi,tab[1].fi,tab[1].se,tab[1].se};
	while(d.b-d.a+1<h || d.d-d.c+1<wi)
	{
		int bg=bs_t(lst,d);
		int tmp=(d.b-d.a+1)*(d.d-d.c+1);
		if(lst<=tmp && tmp<bg)
			ww++;
		lst=bg;
		d=read_t(lst);
	}
	return ww;
}
bool is_ok(int x)
{
	return x==(w[x][1]-w[x][0]+1)*(w[x][3]-w[x][2]+1);
}
void upd(int x)
{
	w[x][0]=min(w[x-1][0],tab[x].fi);
	w[x][1]=max(w[x-1][1],tab[x].fi);
	w[x][2]=min(w[x-1][2],tab[x].se);
	w[x][3]=max(w[x-1][3],tab[x].se);
	return;
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C)
{
	int n=H*W;
	for(int i=1;i<=n;i++)
		tab[i]={R[i-1],C[i-1]};
	if(H<=1000 && W<=1000)
	{
		hw=true;
		solvehw(H,W,R,C);
		return;
	}
	w[0][0]=H;
	w[0][1]=0;
	w[0][2]=W;
	w[0][3]=0;
	for(int i=1;i<=n;i++)
	{
		upd(i);
		ans+=is_ok(i);
	}
	return;
}
int swap_seats(int a,int b)
{
	a++;
	b++;
	if(a>b)
		swap(a,b);
	if(hw)
		return swaphw(a,b);
	swap(tab[a],tab[b]);
	for(int i=a;i<b;i++)
	{
		ans-=is_ok(i);
		upd(i);
		ans+=is_ok(i);
	}
	return ans;
}

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