Submission #103646

#	Time	Username	Problem	Language	Result	Execution time	Memory
103646		figter001	Seats (IOI18_seats)	C++17	5 / 100	4091 ms	69716 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;

pair<int,int> p[kax];
int mnr[4 * kax],mxr[4 * kax],mxc[4 * kax],mnc[4 * kax];
int at,h,w,l,r;

void buildr(int n,int s,int e){
	if(s == e){
		mnr[n] = mxr[n] = p[s-1].first;
		return;
	}
	buildr(n*2,s,(s+e)/2);
	buildr(n*2+1,(s+e)/2+1,e);
	mnr[n] = min(mnr[n*2],mnr[n*2+1]);
	mxr[n] = max(mxr[n*2],mxr[n*2+1]);
}

void buildc(int n,int s,int e){
	if(s == e){
		mnc[n] = mxc[n] = p[s-1].second;
		return;
	}
	buildc(n*2,s,(s+e)/2);
	buildc(n*2+1,(s+e)/2+1,e);
	mnc[n] = min(mnc[n*2],mnc[n*2+1]);
	mxc[n] = max(mxc[n*2],mxc[n*2+1]);
}

void updater(int n,int s,int e){
	if(s > at || e < at)
		return;
	if(s == e){
		mnr[n] = mxr[n] = p[s-1].first;
		return;
	}
	updater(n*2,s,(s+e)/2);
	updater(n*2+1,(s+e)/2+1,e);
	mnr[n] = min(mnr[n*2],mnr[n*2+1]);
	mxr[n] = max(mxr[n*2],mxr[n*2+1]);
}

void updatec(int n,int s,int e){
	if(s > at || e < at)
		return;
	if(s == e){
		mnc[n] = mxc[n] = p[s-1].second;
		return;
	}
	updatec(n*2,s,(s+e)/2);
	updatec(n*2+1,(s+e)/2+1,e);
	mnc[n] = min(mnc[n*2],mnc[n*2+1]);
	mxc[n] = max(mxc[n*2],mxc[n*2+1]);
}

int getmnr(int n,int s,int e){
	if(s > r || e < l)
		return 1e9;
	if(s >= l && e <= r)
		return mnr[n];
	return min(getmnr(n*2,s,(s+e)/2) , getmnr(n*2+1,(s+e)/2+1,e));
}

int getmnc(int n,int s,int e){
	if(s > r || e < l)
		return 1e9;
	if(s >= l && e <= r)
		return mnc[n];
	return min(getmnc(n*2,s,(s+e)/2) , getmnc(n*2+1,(s+e)/2+1,e));
}

int getmxr(int n,int s,int e){
	if(s > r || e < l)
		return 0;
	if(s >= l && e <= r)
		return mxr[n];
	return max(getmxr(n*2,s,(s+e)/2) , getmxr(n*2+1,(s+e)/2+1,e));
}

int getmxc(int n,int s,int e){
	if(s > r || e < l)
		return 0;
	if(s >= l && e <= r)
		return mxc[n];
	return max(getmxc(n*2,s,(s+e)/2) , getmxc(n*2+1,(s+e)/2+1,e));
}

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;
	buildr(1,1,h*w);
	buildc(1,1,h*w);
}

int swap_seats(int a, int b) {
	swap(p[a],p[b]);
	at = a+1;
	updater(1,1,h*w);
	updatec(1,1,h*w);
	at = b+1;
	updater(1,1,h*w);
	updatec(1,1,h*w);
	int ans = 0,cur = 0;
	l = 1;
	while(1){
		if(cur >= h*w)
			break;
		r = cur+1;
		int u = getmnr(1,1,h*w);
		int d = getmxr(1,1,h*w);
		int a = getmnc(1,1,h*w);
		int b = getmxc(1,1,h*w);
		if((d - u + 1) * (b - a + 1) <= cur)
			break;
		// if(cur == 4){
		// 	printf("\n");
		// 	cout << u << ' ' << d << endl;
		// 	cout << a << ' ' << b << endl;
		// 	return 0;
		// }
		if((d - u + 1) * (b - a + 1) == cur + 1){
			ans++;
			cur++;
		}else if((d - u + 1) * (b - a + 1) - 1 > cur){
			cur = (d - u + 1) * (b - a + 1) - 1;
		}
	}

	return ans;
}

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