제출 #116126

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
116126		MvC	자리 배치 (IOI18_seats)	C++14	33 / 100	997 ms	53016 KiB

seats

#pragma GCC optimize("O3")
#include "seats.h"
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<61);
const int inf=(1<<30);
const int nmax=1e6+50;
const int mod=1e9+7;
using namespace std;
int h,w,i,r[nmax],c[nmax],lzy[4*nmax],x,y,p[nmax],q;
pair<int,int>st[4*nmax];
pair<int,int> merge(pair<int,int> x,pair<int,int> y)
{
	if(x.fr<y.fr)return x;
	if(x.fr>y.fr)return y;
	return make_pair(x.fr,x.sc+y.sc);
}
void build(int x,int l,int r)
{
    if(l==r)
    {
        st[x]=make_pair(0,1);
        return;
    }
    int mid=(l+r)/2;
    build(2*x,l,mid);
    build(2*x+1,mid+1,r);
    st[x]=merge(st[2*x],st[2*x+1]);
}
void push(int nod,int l,int r)
{
    if(!lzy[nod])return;
    st[nod].fr+=lzy[nod];
    if(l!=r)
    {
    	lzy[nod*2]+=lzy[nod];
		lzy[nod*2+1]+=lzy[nod];
	}
    lzy[nod]=0;
}
void upd(int nod,int l,int r,int tl,int tr,int v)
{
    push(nod,l,r);
    if(tl<=l && r<=tr)
	{
        lzy[nod]+=v;
        push(nod,l,r);
        return;
    }
    int mid=(l+r)/2;
    if(tl<=mid)upd(nod*2,l,mid,tl,tr,v);
    if(mid<tr)upd(nod*2+1,mid+1,r,tl,tr,v);
    push(nod*2,l,mid);
	push(nod*2+1,mid+1,r);
    st[nod]=merge(st[2*nod],st[2*nod+1]);
}
pair<int,int> qry(int nod,int l,int r,int tl,int tr)
{
    push(nod,l,r);
    if(l>tr || r<tl)return make_pair(inf,0);
    if(tl<=l && r<=tr)return st[nod];
    int mid=(l+r)/2;
    return merge(qry(nod*2,l,mid,tl,tr),qry(nod*2+1,mid+1,r,tl,tr));
}
void give_initial_chart(int H,int W,vector<int>R,vector<int>C)
{
	h=H,w=W;
	for(i=1;i<=h*w;i++)
	{
		r[i]=R[i-1]+1;
		c[i]=C[i-1]+1;
	}
	if(h==1)
	{
		for(i=1;i<=w;i++)p[c[i]]=i;
		p[0]=p[w+1]=w+1;
		build(1,1,w);
		for(i=1;i<=w;i++)
		{
			if(p[c[i]-1]>i && p[c[i]+1]>i)upd(1,1,w,i,w,2);
			else if(p[c[i]-1]<i && p[c[i]+1]<i)upd(1,1,w,i,w,-2);
		}
	}
}
void add(int x,int ps,int cf)
{
	if(p[ps-1]<x)upd(1,1,w,p[ps-1],x-1,cf);
	else upd(1,1,w,x,p[ps-1]-1,cf);
	if(p[ps+1]<x)upd(1,1,w,p[ps+1],x-1,cf);
	else upd(1,1,w,x,p[ps+1]-1,cf);
}
int swap_seats(int x,int y)
{
	if(x>y)swap(x,y);
	x++,y++;
	add(x,c[x],-1);
	add(y,c[y],-1);
	swap(p[c[x]],p[c[y]]);
	swap(c[x],c[y]);
	add(x,c[x],1);
	add(y,c[y],1);
	/*for(i=1;i<=w;i++)
	{
		pair<int,int>pr=qry(1,1,w,i,i);
		if(pr.fr==2)cout<<1<<" ";
		else cout<<0<<" ";
	}
	cout<<endl;*/
	pair<int,int>pr=qry(1,1,w,1,w);
	if(pr.fr==2)return pr.sc;
	return 0;
}
/*int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    cin>>h>>w;
    for(i=1;i<=h*w;i++)
    {
    	cin>>c[i];
	}
	if(h==1)
	{
		for(i=1;i<=w;i++)p[c[i]]=i;
		p[0]=p[w+1]=w+1;
		build(1,1,w);
		for(i=1;i<=w;i++)
		{
			if(p[c[i]-1]>i && p[c[i]+1]>i)upd(1,1,w,i,w,2);
			else if(p[c[i]-1]<i && p[c[i]+1]<i)upd(1,1,w,i,w,-2);
		}
		for(i=1;i<=w;i++)
		{
			cout<<qry(1,1,w,i,i).fr<<" ";
		}
		cout<<endl;
		cin>>q;
		while(q--)
		{
			cin>>x>>y;
			swap_seats(x,y);
			int mn=inf,mx=0;
			for(i=1;i<=w;i++)
			{
				mn=min(mn,c[i]);
				mx=max(mx,c[i]);
				if(mx-mn+1==i)cout<<1<<" ";
				else cout<<0<<" ";
			}
			cout<<endl;
			//cout<<swap_seats(x,y)<<endl;
		}
	}
    return 0;
}*/

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