Submission #766267

#	Time	Username	Problem	Language	Result	Execution time	Memory
766267		amunduzbaev	Seats (IOI18_seats)	C++17	11 / 100	4059 ms	94572 KiB

seats

#include "seats.h"

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

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
typedef long long ll;
typedef int32_t ii;
//~ #define int ll

const int N = 1e6 + 5;
const int inf = 1e9 + 7;

struct ST{
	vector<int> Min, Max;
	int N;
	
	ST(int N): N(N){
		Min.resize(N << 2);
		Max.resize(N << 2);
	}
	
	void set(int i, int v, int lx, int rx, int x){
		if(lx == rx) { Min[x] = Max[x] = v; return; }
		int m = (lx + rx) >> 1;
		if(i <= m) set(i, v, lx, m, x << 1);
		else set(i, v, m + 1, rx, x << 1 | 1);
		Min[x] = min(Min[x << 1], Min[x << 1 | 1]);
		Max[x] = max(Max[x << 1], Max[x << 1 | 1]);
	}
	
	void set(int i, int v){
		set(i, v, 0, N, 1);
	}
	
	int getmax(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l) return 0;
		if(lx >= l && rx <= r) return Max[x];
		
		int m = (lx + rx) >> 1;
		return max(getmax(l, r, lx, m, x << 1), getmax(l, r, m + 1, rx, x << 1 | 1));
	}
	
	int getmax(int l, int r){
		return getmax(l, r, 0, N, 1);
	}
	
	int getmin(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l) return inf;
		if(lx >= l && rx <= r) return Min[x];
		
		int m = (lx + rx) >> 1;
		return min(getmin(l, r, lx, m, x << 1), getmin(l, r, m + 1, rx, x << 1 | 1));
	}
	
	int getmin(int l, int r){
		return getmin(l, r, 0, N, 1);
	}
}X(N), Y(N);


int cnt, sz;
bool is;
vector<int> mnx, mxx, mny, mxy;
vector<int> x, y;

bool check(int i){
	if((mxx[i] - mnx[i] + 1) * (mxy[i] - mny[i] + 1) == i + 1){
		return true;
	}
	
	return false;
}

void give_initial_chart(int n, int m, vector<int> r, vector<int> c) {
	sz = n * m;
	mnx.resize(sz);
	mxx.resize(sz);
	mny.resize(sz);
	mxy.resize(sz);
	swap(x, r);
	swap(y, c);
	
	cnt = 0;
	for(int i=0;i<sz;i++){
		mnx[i] = mxx[i] = x[i];
		mny[i] = mxy[i] = y[i];
		if(i){
			mnx[i] = min(mnx[i], mnx[i - 1]);
			mny[i] = min(mny[i], mny[i - 1]);
			mxx[i] = max(mxx[i], mxx[i - 1]);
			mxy[i] = max(mxy[i], mxy[i - 1]);
		}
		
		if(check(i)) cnt++;
	}
	
	is = 0;
	if(max(n, m) <= 1000){
		is = 1;
	}
	
	for(int i=0;i<sz;i++){
		X.set(i, x[i]);
		Y.set(i, y[i]);
	}
}

int ans(int i, int j){
	swap(x[i], x[j]), swap(y[i], y[j]);
	X.set(i, x[i]), Y.set(i, y[i]);
	X.set(j, x[j]), Y.set(j, y[j]);
	int last = 0, res = 0, cnt = 0;
	while(last < sz){
		int mnx = X.getmin(0, last);
		int mxx = X.getmax(0, last);
		int mny = Y.getmin(0, last);
		int mxy = Y.getmax(0, last);
		int area = (mxx - mnx + 1) * (mxy - mny + 1);
		if(area == last + 1){
			last++;
			res++;
		} else {
			last = area - 1;
		}
		cnt++;
	}
	
	assert(cnt <= 4000);
	
	return res;
}

int swap_seats(int i, int j){
	if(i > j) swap(i, j);
	if(is){
		return ans(i, j);
	}
	
	swap(x[i], x[j]);
	swap(y[i], y[j]);
	
	for(int k=i;k<=j;k++){
		if(check(k)) cnt--;
		mnx[k] = mxx[k] = x[k];
		mny[k] = mxy[k] = y[k];
		if(k){
			mnx[k] = min(mnx[k], mnx[k - 1]);
			mny[k] = min(mny[k], mny[k - 1]);
			mxx[k] = max(mxx[k], mxx[k - 1]);
			mxy[k] = max(mxy[k], mxy[k - 1]);
		}
		
		if(check(k)) cnt++;
	}
	
	return cnt;
}

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