제출 #80400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
80400		KLPP	자리 배치 (IOI18_seats)	C++14	11 / 100	4086 ms	42044 KiB

seats

#include "seats.h"
#include<iostream>
#include<vector>

using namespace std;
typedef long long int lld;
typedef pair<int,int> pii;
int h,w;
int r[1000010];
int c[1000010];
pii arr[1000010];
//segtree
pii sum[8000000];
pii minimo[8000000];
pii counter[8000000];
vector<vector<int> >table;
void update_pos(int a, int b){
	if(a<0 || a>h-1)return;
	if(b<0 || b>w-1)return;
	int t[3][3];
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++)t[i][j]=1;
	}//cout<<a<<" "<<b<<endl;
	t[1][1]=0;
	if(a==0 || b==0 || table[a-1][b-1]>table[a][b])t[0][0]=0;
	if(a==0 || b==w-1 || table[a-1][b+1]>table[a][b])t[0][2]=0;
	if(a==h-1 || b==0 || table[a+1][b-1]>table[a][b])t[2][0]=0;
	if(a==h-1 || b==w-1 || table[a+1][b+1]>table[a][b])t[2][2]=0;
	if(a==0 || table[a-1][b]>table[a][b])t[0][1]=0;
	if(b==0 || table[a][b-1]>table[a][b])t[1][0]=0;
	if(a==h-1 || table[a+1][b]>table[a][b])t[2][1]=0;
	if(b==w-1 || table[a][b+1]>table[a][b])t[1][2]=0;
	/*for(int i=0;i<3;i++){
		for(int j=0;j<3;j++)cout<<t[i][j];
		cout<<endl;
	}cout<<endl;*/
	int x,y,z,w;
	x=t[0][0]+t[0][1]+t[1][0]+t[1][1];
	y=t[1][0]+t[1][1]+t[2][0]+t[2][1];
	z=t[0][1]+t[0][2]+t[1][1]+t[1][2];
	w=t[1][1]+t[1][2]+t[2][1]+t[2][2];
	int cnt[5];
	for(int i=0;i<5;i++)cnt[i]=0;
	cnt[x]++;
	cnt[y]++;
	cnt[z]++;
	cnt[w]++;
	//cout<<table[a][b]<<" "<<x<<endl;
	//cout<<cnt[0]-cnt[1]<<endl;
	arr[table[a][b]].first=cnt[0]-cnt[1];
	arr[table[a][b]].second=cnt[2]-cnt[3];
}
void build(int a, int b, int node){
	/*if(a==b){
		sum[node]=arr[a];
		minimo[node]=arr[a];
		counter[node]=1;
		return;
	}
	int mid=(a+b)/2;
	build(a,mid,2*node);
	build(mid+1,b,2*node+1);
	sum[node]=sum[2*node]+sum[2*node+1];
	minimo[node]=min(minimo[2*node],minimo[2*node+1]+sum[2*node]);
	counter[node]=0;
	if(minimo[node]==minimo[2*node]){
		counter[node]+=counter[2*node];
	}
	if(minimo[node]==minimo[2*node+1]+sum[2*node]){
		counter[node]+=counter[2*node+1];
	}*/
}
void update(int a, int b, int node, int pos){
	/*if(pos<a || b<pos)return;
	if(a==b){
		sum[node]=arr[a];
		minimo[node]=arr[a];
		counter[node]=1;
		return;
	}
	int mid=(a+b)/2;
	update(a,mid,2*node,pos);
	update(mid+1,b,2*node+1,pos);
	sum[node]=sum[2*node]+sum[2*node+1];
	minimo[node]=min(minimo[2*node],minimo[2*node+1]+sum[2*node]);
	counter[node]=0;
	if(minimo[node]==minimo[2*node]){
		counter[node]+=counter[2*node];
	}
	if(minimo[node]==minimo[2*node+1]+sum[2*node]){
		counter[node]+=counter[2*node+1];
	}*/
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	h=H;
	w=W;
	for(int i=0;i<h;i++){
		vector<int> a;
		for(int j=0;j<w;j++)a.push_back(-1);
		table.push_back(a);
	}
	for(int i=0;i<w*h;i++){
		r[i]=R[i];
		c[i]=C[i];
		table[R[i]][C[i]]=i;
	}
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++)update_pos(i,j);
	}
	//build(0,w-1,1);
	//for(int i=0;i<h*w;i++)cout<<arr[i].second<<endl;
}

int swap_seats(int a, int b) {
	swap(table[r[a]][c[a]],table[r[b]][c[b]]);
	swap(r[a],r[b]);
	swap(c[a],c[b]);
	for(int i=-1;i<2;i++){
		for(int j=-1;j<2;j++){
			update_pos(r[a]+i,c[a]+j);
			update_pos(r[b]+i,c[b]+j);
		}
	}
	
	/*int pos_a=inv[a];
	int pos_b=inv[b];
	swap(inv[a],inv[b]);
	swap(per[pos_a],per[pos_b]);
	update_pos(a);
	update(0,w-1,1,a);
	update_pos(b);
	update(0,w-1,1,b);
	if(inv[a]>0){
		update_pos(per[inv[a]-1]);
		update(0,w-1,1,per[inv[a]-1]);
	}
	if(inv[a]<w-1){
		update_pos(per[inv[a]+1]);
		update(0,w-1,1,per[inv[a]+1]);
	}
	if(inv[b]>0){
		update_pos(per[inv[b]-1]);
		update(0,w-1,1,per[inv[b]-1]);
	}
	if(inv[b]<w-1){
		update_pos(per[inv[b]+1]);
		update(0,w-1,1,per[inv[b]+1]);
	}*/
	//for(int i=0;i<w;i++)cout<<arr[i]<<endl;
	//return counter[1];
	int cnt=0;
	int one=0;
	int three=0;
	for(int i=0;i<h*w;i++){
		three+=arr[i].second;
		one+=arr[i].first;
		if(one==4 && three==0){
			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