Submission #103649

#	Time	Username	Problem	Language	Result	Execution time	Memory
103649		figter001	Seats (IOI18_seats)	C++17	25 / 100	4077 ms	73692 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{
	int u,d,a,b;
}seg[3*kax];

pair<int,int> 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)1e9,0,(int)1e9,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 >= h*w)
			break;
		r = cur+1;
		node g = get(1,1,n);
		int u = g.u;
		int d = g.d;
		int a = g.a;
		int b = g.b;
		if((d - u + 1) * (b - a + 1) == cur + 1){
			ans++;
			cur++;
		}else{
			cur = (d - u + 1) * (b - a + 1) - 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