Submission #766536

#	Time	Username	Problem	Language	Result	Execution time	Memory
766536		amunduzbaev	Seats (IOI18_seats)	C++17	37 / 100	4062 ms	126576 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

int cnt, sz, n, m;
bool is;
vector<int> mnx_, mxx_, mny_, mxy_;
deque<ar<int, 2>> mnx, mxx, mny, mxy;
vector<int> x, y;
vector<set<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 h, int w, vector<int> r, vector<int> c) {
	n = h, m = w;
	sz = n * m;
	X.resize(n), Y.resize(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[x[i]].insert(i);
			Y[y[i]].insert(i);
			//~ X.set(i, x[i]);
			//~ Y.set(i, y[i]);
		}
		
		for(int i=n-1;~i;i--){
			int p = *X[i].begin();
			if(mxx.empty() || p < mxx[0][0]) mxx.push_front({p, i});
			while(!mnx.empty() && mnx.back()[0] > p) mnx.pop_back();
			mnx.push_back({p, i});
		}
		
		for(int i=m-1;~i;i--){
			int p = *Y[i].begin();
			if(mxy.empty() || p < mxy[0][0]) mxy.push_front({p, i});
			while(!mny.empty() && mny.back()[0] > p) mny.pop_back();
			mny.push_back({p, i});
		}
	}
}

int ans(int i, int j){
	X[x[i]].erase(i), Y[y[i]].erase(i);
	X[x[j]].erase(j), Y[y[j]].erase(j);
	swap(x[i], x[j]), swap(y[i], y[j]);
	X[x[i]].insert(i), Y[y[i]].insert(i);
	X[x[j]].insert(j), Y[y[j]].insert(j);
	mxx.clear(), mnx.clear();
	for(int i=n-1;~i;i--){
		int p = *X[i].begin();
		if(mxx.empty() || p < mxx[0][0]) mxx.push_front({p, i});
		while(!mnx.empty() && mnx.back()[0] > p) mnx.pop_back();
		mnx.push_back({p, i});
	}
	mxy.clear(), mny.clear();
	for(int i=m-1;~i;i--){
		int p = *Y[i].begin();
		if(mxy.empty() || p < mxy[0][0]) mxy.push_front({p, i});
		while(!mny.empty() && mny.back()[0] > p) mny.pop_back();
		mny.push_back({p, i});
	}
	
	//~ for(auto x : mxx) cout<<x[0]<<" ";
	//~ cout<<"\n";
	//~ for(auto x : mnx) cout<<x[0]<<" ";
	//~ cout<<"\n";
	//~ for(auto x : mxy) cout<<x[0]<<" ";
	//~ cout<<"\n";
	//~ for(auto x : mny) cout<<x[0]<<" ";
	//~ cout<<"\n";
	//~ cout<<"here"<<endl;
	
	int last = 1, res = 1, cnt = 0;
	while(last < sz){
		int mnx_ = (*--lower_bound(mnx.begin(), mnx.end(), (ar<int, 2>){last + 1, 0}))[1];
		int mxx_ = (*--lower_bound(mxx.begin(), mxx.end(), (ar<int, 2>){last + 1, 0}))[1];
		int mny_ = (*--lower_bound(mny.begin(), mny.end(), (ar<int, 2>){last + 1, 0}))[1];
		int mxy_ = (*--lower_bound(mxy.begin(), mxy.end(), (ar<int, 2>){last + 1, 0}))[1];
		int area = (mxx_ - mnx_ + 1) * (mxy_ - mny_ + 1);
		if(area == last + 1){
			last++;
			res++;
		} else {
			last = area - 1;
		}
		cnt++;
	}
	
	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: 20 / 20
• Subtask 4: 6 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30