제출 #420354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420354		Jasiekstrz	Seats (IOI18_seats)	C++17	5 / 100	4061 ms	66388 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 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;
}
pair<int,int> 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 make_pair(ww.b-ww.a+1,ww.d-ww.c+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;
	pair<int,int> d={1,1};
	while(d!=make_pair(h,wi))
	{
		int bg=1,en=h*wi;
		while(bg<en)
		{
			int mid=(bg+en)/2;
			auto v=read_t(mid);
			if(v.fi<=d.fi && v.se<=d.se)
				bg=mid+1;
			else
				en=mid;
		}
		if(lst<=d.fi*d.se && d.fi*d.se<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: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30