제출 #138765

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
138765		MoNsTeR_CuBe	자리 배치 (IOI18_seats)	C++17	5 / 100	4074 ms	87160 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;
 
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 root, int left, int right){
	if(left == right){
		maxi[root].second = mini[root].second = v[left-1].second;
		maxi[root].first = mini[root].first = v[left-1].first;
		return;
	}
	int mid = (left+right)>>1;
	
	Build(root<<1, left, mid);
	Build(root<<1|1, mid+1, right);
	update(root);
}
 
void update(int root, int left, int right, int index, pair<int, int> p){
	if(left > index || right < index) return;
	if(left == index && right == index){
		maxi[root].second = mini[root].second = p.second;
		maxi[root].first = mini[root].first = p.first;
		return;
	}
	int mid = (left+right)>>1;
	update(root<<1, left, mid, index, p);
	update(root<<1|1, mid+1, right, index, p);
	update(root);
}
 
tuple<int, int, int, int> query(int root, int left, int right, int qLeft, int qRight){
	if(left > qRight || right < qLeft) return {INT_MAX, INT_MAX, INT_MIN, INT_MIN};
	if(left >= qLeft && right <= qRight){
		return {mini[root].first, mini[root].second, maxi[root].first, maxi[root].second};
	}
	int mid = (left+right)>>1;
	tuple<int, int, int, int> p = query(root<<1, left, mid, qLeft, qRight);
	tuple<int, int, int, int> q = query(root<<1|1, mid+1, right, qLeft, qRight);
	
	return {min(get<0>(p), get<0>(q)), min(get<1>(p), get<1>(q)), max(get<2>(p), get<2>(q)), max(get<3>(p), get<3>(q))};
}
 
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)<<2);
	maxi.resize((h*w+1)<<2);
	for(int i = 0; i < H*W; i++){
		v[i] = make_pair(R[i], C[i]);
	}
	Build(1, 1, H*W);
}
int swap_seats(int a, int b) {
	update(1, 1, h*w, a+1, v[b]);
	update(1, 1, h*w, b+1, 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(1, 1, h*w, 1, curr);
		pair<int, int> maxii = {get<2>(q), get<3>(q)};
		pair<int, int> minii  = {get<0>(q), get<1>(q)};
		//cout << curr << endl;
		//cout << maxii.first << ' ' << maxii.second << ' ' << minii.first << ' ' << minii.second << endl;
		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: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30