Submission #138761

#	Time	Username	Problem	Language	Result	Execution time	Memory
138761		MoNsTeR_CuBe	Seats (IOI18_seats)	C++17	25 / 100	4094 ms	55800 KiB

seats

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

inline int min(int &a, int &b){
	if(a < b) return a;
	return b;
}

inline int max(int &a, int &b){
	if(a < b) return b;
	return a;
}

vector< pair<int, int > > mini;
vector< pair<int, int > > maxi;

inline void update(int root){
	mini[root].first = min(mini[root<<1].first, mini[root<<1|1].first);
	mini[root].second = min(mini[root<<1].second, mini[root<<1|1].second);
	maxi[root].first = max(maxi[root<<1].first, maxi[root<<1|1].first);
	maxi[root].second = max(maxi[root<<1].second, maxi[root<<1|1].second);
}

vector< pair<int, int> > v;

void Build(int right){
	for(int root = (right<<1)-1; root >= right; root--){
		//cout << "SET " << root << endl;
		maxi[root].first = mini[root].first = v[root-right].first;
		maxi[root].second = mini[root].second = v[root-right].second;
	}
	for(int i = right-1; i > 0; i--){
		update(i);
	}
}

void update(int right, int index, pair<int, int> p){
	index += right;
	maxi[index].first = mini[index].first = p.first;
	maxi[index].second = mini[index].second = p.second;
	index >>=1;;
	
	while(index){
		update(index);
		index>>=1;
	}
}

tuple<int, int, int, int> query(int right, int qLeft, int qRight){
	qLeft += right;
	qRight += right;
	
	tuple<int, int, int, int> tup = {INT_MAX, INT_MAX, INT_MIN, INT_MIN};
	
	while(qLeft < qRight){
		if(qLeft&1){
			tup = {min(get<0>(tup), mini[qLeft].first), min(get<1>(tup), mini[qLeft].second), max(get<2>(tup), maxi[qLeft].first), max(get<3>(tup), maxi[qLeft].second)};
			qLeft++;
		}
		if(qRight&1){
			qRight--;
			tup = {min(get<0>(tup), mini[qRight].first), min(get<1>(tup), mini[qRight].second), max(get<2>(tup), maxi[qRight].first), max(get<3>(tup), maxi[qRight].second)};
		}
		qLeft >>= 1;
		qRight >>= 1;
	}
	
	return tup;
}

int h, w;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { 
	h = H;
	w = W;
	v.resize(h*w);
	mini.resize((h*w+1)<<1);
	maxi.resize((h*w+1)<<1);
	for(int i = 0; i < H*W; i++){
		v[i] = make_pair(R[i], C[i]);
	}
	Build(H*W);
}
int swap_seats(int a, int b) {
	update(h*w, a, v[b]);
	update(h*w, b, v[a]);
	
	//cout << "MIAOU" << endl;
	
	swap(v[b], v[a]);
	int curr = 1;
	int ans = 0;
	while(curr <= h*w){
		tuple<int, int, int, int> q = query(h*w, 0, curr);
		pair<int, int> maxii = {get<2>(q), get<3>(q)};
		pair<int, int> minii  = {get<0>(q), get<1>(q)};
		if((maxii.first - minii.first + 1)*(maxii.second - minii.second + 1) == curr){
			ans++;
			curr++;
		}else{
			assert((maxii.first - minii.first + 1)*(maxii.second - minii.second + 1) > curr);
			curr = (maxii.first - minii.first + 1)*(maxii.second - minii.second + 1);
		}
		//cout << ans << endl;
	}
	
	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