제출 #423195

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
423195		Jasiekstrz	자리 배치 (IOI18_seats)	C++17	0 / 100	2946 ms	262148 KiB

seats

#warning H=1
#include<bits/stdc++.h>
#include "seats.h"
#define fi first
#define se second
using namespace std;
const int N=1e6;
const int PP=11e5;
const int INF=1e9+7;
struct Mn
{
	int w,cnt;
	Mn(int _w=0,int _cnt=0) : w(_w), cnt(_cnt) {};
	void operator+=(const Mn &oth)
	{
		if(oth.w<w && oth.cnt>0)
		{
			w=oth.w;
			cnt=oth.cnt;
		}
		else if(oth.w==w)
			cnt+=oth.cnt;
		return;
	}
	Mn operator+(const Mn &oth)
	{
		Mn tmp=*this;
		tmp+=oth;
		return tmp;
	}
	bool operator<(const Mn &oth) const
	{
		return w<oth.w;
	}
};
struct Tree
{
	Mn ans,ansc0,ansd0;
	int c,d;
	set<int> sty;
};
int n,hi,wi;
pair<int,int> tab[N+10];
int pot;
Tree tree[2*PP+10];
tuple<Mn,Mn,Mn> dfs(int i,int l,int r,int c,int d)
{
	//cerr<<i<<" "<<l<<" "<<r<<" "<<c<<" "<<d<<"\n";
	if(l==r)
	{
		//cerr<<"xd1\n";
		Mn w=max(tree[i].ans,Mn(d-c+1-min(n,r),(r<=n)));
		Mn c0=max(tree[i].ansc0,Mn(d+1-min(n,r),(r<=n)));
		Mn d0=max(tree[i].ansd0,Mn(-c+1-min(n,r),(r<=n)));
		return {w,c0,d0};
	}
	if(tree[2*i+1].d<=d)
	{
		//cerr<<"xd2\n";
		auto [w,c0,d0]=dfs(i,l,r,c,-1);
		c0={d+1-min(n,r),1};
		w={d0.w+d,d0.cnt};
		return {w,c0,d0};
	}
	if(tree[2*i+1].c>=c)
	{
		//cerr<<"xd3\n";
		auto [w,c0,d0]=dfs(i,l,r,wi+1,d);
		d0={-c+1-min(n,r),1};
		w={c0.w-c,c0.cnt};
		return {w,c0,d0};
	}
	bool brc,brd;
	brc=(tree[2*i].c>=c);
	brd=(tree[2*i].d<=d);
	int mid=(l+r)/2;
	if(brc && brd)
	{
		//cerr<<"xd4\n";
		auto [w,c0,d0]=dfs(2*i+1,mid+1,r,c,d);
		w+=Mn(d-c+1-min(n,r),1);
		c0+=Mn(d+1-min(n,r),1);
		d0+=Mn(-c+1-min(n,r),1);
		return {w,c0,d0};
	}
	if(brc)
	{
		//cerr<<"xd5\n";
		auto [w,c0,d0]=dfs(2*i+1,mid+1,r,c,-1);
		auto [w1,c01,d01]=dfs(2*i,l,mid,c,d);
		w+=w1;
		c0+=c01;
		d0+=d01;
		return {w,c0,d0};
	}
	if(brd)
	{
		//cerr<<"xd6\n";
		auto [w,c0,d0]=dfs(2*i+1,mid+1,r,wi+1,d);
		auto [w1,c01,d01]=dfs(2*i,l,mid,c,d);
		w+=w1;
		c0+=c01;
		d0+=d01;
		return {w,c0,d0};
	}
	//cerr<<"xd7\n";
	auto [w,c0,d0]=dfs(2*i,l,mid,c,d);
	w+=tree[2*i+1].ans;
	c0+=tree[2*i+1].ansc0;
	d0+=tree[2*i+1].ansd0;
	return {w,c0,d0};
}
void solve(int i,int l,int r)
{
	//cerr<<"solve "<<i<<" "<<l<<" "<<r<<"\n";
	if(l==r)
	{
		tree[i].c=wi;
		tree[i].d=0;
		tree[i].ans=Mn(-INF,0);
		tree[i].ansc0=Mn(-INF,0);
		tree[i].ansd0=Mn(-INF,0);
		if(!tree[i].sty.empty())
		{
			int c=*tree[i].sty.begin(),d=*prev(tree[i].sty.end());
			tree[i].c=min(tree[i].c,c);
			tree[i].d=max(tree[i].d,d);
			tree[i].ans=Mn(tree[i].d-tree[i].c+1-min(n,r),(r<=n));
			tree[i].ansc0=Mn(tree[i].d+1-min(n,r),(r<=n));
			tree[i].ansd0=Mn(-tree[i].c+1-min(n,r),(r<=n));
		}
		return;
	}
	tree[i].c=min(tree[2*i].c,tree[2*i+1].c);
	tree[i].d=max(tree[2*i].d,tree[2*i+1].d);
	tree[i].ans=tree[2*i].ans+tree[2*i+1].ans;
	tree[i].ansc0=tree[2*i].ansc0+tree[2*i+1].ansc0;
	tree[i].ansd0=tree[2*i].ansd0+tree[2*i+1].ansd0;
	if(tree[i].sty.empty())
		return;
	int c=*tree[i].sty.begin(),d=*prev(tree[i].sty.end());
	tree[i].c=min(tree[i].c,c);
	tree[i].d=max(tree[i].d,d);
	auto [t0,t1,t2]=dfs(i,l,r,c,d);
	tree[i].ans=t0;
	tree[i].ansc0=t1;
	tree[i].ansd0=t2;
	return;
}
void del_t(int i,int l,int r,int ls,int rs,pair<int,int> c)
{
	if(rs<l || r<ls)
		return;
	if(ls<=l && r<=rs)
	{
		tree[i].sty.erase(c.se);
		solve(i,l,r);
		return;
	}
	int mid=(l+r)/2;
	del_t(2*i,l,mid,ls,rs,c);
	del_t(2*i+1,mid+1,r,ls,rs,c);
	solve(i,l,r);
	return;
}
void add_t(int i,int l,int r,int ls,int rs,pair<int,int> c)
{
	if(rs<l || r<ls)
		return;
	if(ls<=l && r<=rs)
	{
		tree[i].sty.insert(c.se);
		solve(i,l,r);
		return;
	}
	int mid=(l+r)/2;
	add_t(2*i,l,mid,ls,rs,c);
	add_t(2*i+1,mid+1,r,ls,rs,c);
	solve(i,l,r);
	return;
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C)
{
	n=H*W;
	hi=H;
	wi=W;
	for(int i=1;i<=n;i++)
		tab[i]={R[i-1],C[i-1]};
	for(pot=1;pot<n;pot*=2);
	for(int i=2*pot-1;i>=1;i--)
	{
		tree[i].c=wi;
		tree[i].d=0;
		tree[i].ans=Mn(-INF,0);
		tree[i].ansc0=Mn(-INF,0);
		tree[i].ansd0=Mn(-INF,0);
	}
#warning buid tree faster
	for(int i=1;i<=n;i++)
		add_t(1,1,pot,i,n,tab[i]);
	//for(int i=1;i<2*pot;i++)
	//	cerr<<"tree["<<i<<"].ans=("<<tree[i].ans.w<<","<<tree[i].ans.cnt<<") c="<<tree[i].c<<" d="<<tree[i].d<<"\n";
	return;
}
int swap_seats(int a,int b)
{
	a++;
	b++;
	del_t(1,1,pot,a,n,tab[a]);
	del_t(1,1,pot,b,n,tab[b]);
	swap(tab[a],tab[b]);
	add_t(1,1,pot,a,n,tab[a]);
	add_t(1,1,pot,b,n,tab[b]);
	//for(int i=1;i<2*pot;i++)
	//	cerr<<"tree["<<i<<"].ans=("<<tree[i].ans.w<<","<<tree[i].ans.cnt<<") c="<<tree[i].c<<" d="<<tree[i].d<<"\n";
	return tree[1].ans.cnt;
}

컴파일 시 표준 에러 (stderr) 메시지

seats.cpp:1:2: warning: #warning H=1 [-Wcpp]
    1 | #warning H=1
      |  ^~~~~~~
seats.cpp:198:2: warning: #warning buid tree faster [-Wcpp]
  198 | #warning buid tree faster
      |  ^~~~~~~

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