제출 #286011

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
286011		AlanChen	자리 배치 (IOI18_seats)	C++14	25 / 100	4075 ms	72192 KiB

seats

#include "seats.h"


#include <bits/stdc++.h>
using namespace std;



template<class A> using v=vector<A>;
template<class A,class B> using p=pair<A,B>;

typedef p<int,int> pi;
typedef v<int> vi;
typedef v<pi> vpi;
typedef string str;

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define sz(S) (int)S.size()

#define get4(a,b,c,d,...) d

#define lp3(x,a,b) for(int x=(a);x<(b);x++)
#define lp2(x,a) lp3(x,0,a)
#define lp1(a) lp2(loopvar,a)
#define lp(x...) get4(x,lp3,lp2,lp1,0)(x)

#define lr3(x,a,b) for(int x=(b)-1;x>=(a);x--)
#define lr2(x,a) lr3(x,0,a)
#define lr1(a) lr2(looprvar,a)
#define lr(x...) get4(x,lr3,lr2,lr1,0)(x)


#define trv(x,S) for(auto& x:(S))


template <class A,class B> bool ckmax(A& a1,const B& b1) {return a1<b1?a1=b1,1:0;}
template <class A,class B> bool ckmin(A& a1,const B& b1) {return a1>b1?a1=b1,1:0;}









const int mx=1001000;

p<pi,pi> merger (const p<pi,pi>& i1,const p<pi,pi>& i2)
{
	return mp(
			mp(min(i1.f.f,i2.f.f),max(i1.f.s,i2.f.s)),
			mp(min(i1.s.f,i2.s.f),max(i1.s.s,i2.s.s))
	);
}

struct seg
{
	p<pi,pi> dat[mx*2];
	void init()
	{
		lr(i,1,mx) pull(i);
	}
	void pull(int x) {dat[x]=merger(dat[2*x],dat[2*x+1]);}
	void updt(int x,const p<pi,pi>& v) {dat[x+=mx]=v; for(x/=2;x>0;x/=2) pull(x);}
	pi query(int x,int y)
	{
		p<pi,pi> ans(mp(mx,-1),mp(mx,-1)); for(x+=mx,y+=mx;x<y;x/=2,y/=2)
		{
			if(x%2==1) ans=merger(ans,dat[x++]);
			if(y%2==1) ans=merger(ans,dat[--y]);
		}
		return mp((ans.f.s-ans.f.f+1),(ans.s.s-ans.s.f+1));
	}
};

int h,w;
int pos[mx][2];






seg bd;



void give_initial_chart(int H, int W, vi R, vi C)
{
	h=H,w=W;
	lp(i,h*w) pos[i][0]=R[i],pos[i][1]=C[i];

	lp(i,h*w) bd.dat[i+mx].f=mp(pos[i][0],pos[i][0]);
	lp(i,h*w) bd.dat[i+mx].s=mp(pos[i][1],pos[i][1]);

	bd.init();
}



int swap_seats(int a, int b)
{
	bd.updt(a,mp( mp(pos[b][0],pos[b][0]),mp(pos[b][1],pos[b][1])  ));
	bd.updt(b,mp( mp(pos[a][0],pos[a][0]),mp(pos[a][1],pos[a][1])  ));
	lp(dim,2) swap(pos[a][dim],pos[b][dim]);

	int ans=0;
	int idx=1;
	while(idx<=h*w)
	{
		int tmp[2];
		tie(tmp[0],tmp[1])=bd.query(0,idx);
		if(tmp[0]*tmp[1]==idx)
		{
			ans++;
			idx+=min(tmp[0],tmp[1]);
		}
		else idx=tmp[0]*tmp[1];
	}

	return ans;
}

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