제출 #103651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103651		figter001	자리 배치 (IOI18_seats)	C++17	25 / 100	4077 ms	36756 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 1010;
const int kax = nax*nax;

struct node{
	short u,d,a,b;
}seg[3*kax];

pair<short,short> p[kax];
int at,h,w,l,r,cnt,n;

void build(int n,int s,int e){
	if(s == e){
		seg[n] = {p[s-1].first,p[s-1].first,p[s-1].second,p[s-1].second};
		return;
	}
	build(n*2,s,(s+e)/2);
	build(n*2+1,(s+e)/2+1,e);
	seg[n] = {min(seg[n*2].u,seg[n*2+1].u) , max(seg[n*2].d,seg[n*2+1].d) ,
				min(seg[n*2].a,seg[n*2+1].a) , max(seg[n*2].b,seg[n*2+1].b) };
}

void update(int n,int s,int e){
	if(s == e){
		seg[n] = {p[s-1].first,p[s-1].first,p[s-1].second,p[s-1].second};
		return;
	}
	if((s+e)/2 >= at)
		update(n*2,s,(s+e)/2);
	if((s+e)/2+1 <= at)
	update(n*2+1,(s+e)/2+1,e);
	seg[n] = {min(seg[n*2].u,seg[n*2+1].u) , max(seg[n*2].d,seg[n*2+1].d) ,
				min(seg[n*2].a,seg[n*2+1].a) , max(seg[n*2].b,seg[n*2+1].b) };
}

node get(int n,int s,int e){
	if(s >= l && e <= r)
		return seg[n];
	node x,y,z;
	x = y = {(int)1e4,0,(int)1e4,0};
	if((s+e)/2 >= l)
		x = get(n*2,s,(s+e)/2);
	if((s+e)/2+1 <= r)
		y = get(n*2+1,(s+e)/2+1,e);
	z = {min(x.u,y.u) , max(x.d,y.d) , min(x.a,y.a) , max(x.b,y.b) };
	return z;
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	for(int i=0;i<H*W;i++)
		p[i] = {R[i],C[i]};
	h = H;
	w = W;
	n = h*w;
	build(1,1,n);
}

int swap_seats(int a, int b) {
	swap(p[a],p[b]);
	at = a+1;
	update(1,1,n);
	at = b+1;
	update(1,1,n);
	int ans = 0,cur = 0;
	l = 1;
	while(1){
		if(cur >= n)
			break;
		cnt++;
		r = cur+1;
		node g = get(1,1,n);
		short u = g.u;
		short d = g.d;
		short a = g.a;
		short b = g.b;
		int q = (d - u + 1) * (b - a + 1);
		if(q == cur + 1){
			ans++;
			cur++;
		}else{
			cur = q - 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