제출 #138355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
138355		MoNsTeR_CuBe	자리 배치 (IOI18_seats)	C++17	5 / 100	4082 ms	133800 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
 
struct node{
	node *l, *r;
	
	pair<int, int> mini;
	pair<int, int> maxi;
	
	void update(){
		mini.first = min(l->mini.first, r->mini.first);
		mini.second = min(l->mini.second, r->mini.second);
		
		maxi.first = max(l->maxi.first, r->maxi.first);
		maxi.second = max(l->maxi.second, r->maxi.second);
	}
};
 
vector< pair<int, int> > v;
 
void Build(node* root, int left, int right){
	if(left == right){
		root->maxi.second = root->mini.second = v[left-1].second;
		root->maxi.first = root->mini.first = v[left-1].first;
		return;
	}
	int mid = (left+right)/2;
	
	if(!root->l) root->l = new node{NULL,NULL,{0,0},{0,0}};
	if(!root->r) root->r = new node{NULL,NULL,{0,0},{0,0}};
	Build(root->l, left, mid);
	Build(root->r, mid+1, right);
	root->update();
}
 
void update(node* root, int left, int right, int index, pair<int, int> p){
	if(left > index || right < index) return;
	if(left == right){
		root->maxi.second = root->mini.second = p.second;
		root->maxi.first = root->mini.first = p.first;
		return;
	}
	int mid = (left+right)/2;
	update(root->l, left, mid, index, p);
	update(root->r, mid+1, right, index, p);
	root->update();
}
 
pair<int, int> queryMin(node* root, int left, int right, int qLeft, int qRight){
	if(left > qRight || right < qLeft) return {INT_MAX, INT_MAX};
	if(left >= qLeft && right <= qRight){
		return root->mini;
	}
	int mid = (left+right)/2;
	pair<int, int> p = queryMin(root->l, left, mid, qLeft, qRight);
	pair<int, int> q = queryMin(root->r, mid+1, right, qLeft, qRight);
	
	return {min(p.first, q.first), min(p.second, q.second)};
}
 
pair<int, int> queryMax(node* root, int left, int right, int qLeft, int qRight){
	if(left > qRight || right < qLeft) return {INT_MIN, INT_MIN};
	if(left >= qLeft && right <= qRight){
		return root->maxi;
	}
	int mid = (left+right)/2;
	pair<int, int> p = queryMax(root->l, left, mid, qLeft, qRight);
	pair<int, int> q = queryMax(root->r, mid+1, right, qLeft, qRight);
	
	return {max(p.first, q.first), max(p.second, q.second)};
}
 
int h, w;
 
node* root = new node{NULL,NULL,{0,0},{0,0}};
 
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { 
	h = H;
	w = W;
	v.resize(h*w);
	for(int i = 0; i < H*W; i++){
		v[i] = make_pair(R[i], C[i]);
	}
	Build(root, 1, H*W);
}
 
int swap_seats(int a, int b) {
	update(root, 1, h*w, a+1, v[b]);
	update(root, 1, h*w, b+1, v[a]);
	
	swap(v[b], v[a]);
	int curr = 1;
	int ans = 0;
	while(curr <= h*w){
		pair<int, int> mini = queryMin(root, 1, h*w, 1, curr);
		pair<int, int> maxi = queryMax(root, 1, h*w, 1, curr);
		//if(curr == 5) break;
		if((maxi.first - mini.first + 1)*(maxi.second - mini.second + 1) == curr){
			ans++;
			curr++;
		}else{
			curr = (maxi.first - mini.first + 1)*(maxi.second - mini.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