제출 #80274

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

seats

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

using namespace std;
typedef long long int lld;
int h,w;
int per[1000010];
int inv[1000010];
int arr[1000010];
//segtree
int sum[8000000];
int minimo[8000000];
int counter[8000000];
int cnt;
void update_pos(int i){
	int pos=inv[i];
	arr[i]=-1;
	if(pos==0 || per[pos-1]>i){
		arr[i]++;
	}
	if(pos==w-1 || per[pos+1]>i){
		arr[i]++;
	}
}
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) {cnt=0;
	h=H;
	w=W;
	for(int i=0;i<w;i++){
		inv[i]=C[i];
		per[C[i]]=i;
	}
	for(int i=0;i<w;i++){
		int pos=inv[i];
		arr[i]=-1;
		if(pos==0 || per[pos-1]>i){
			arr[i]++;
		}
		if(pos==w-1 || per[pos+1]>i){
			arr[i]++;
		}
		//cout<<arr[i]<<endl;
	}
	build(0,w-1,1);	
	//cout<<counter[1]<<endl;
	/*for(int i=1;i<8;i++){
		cout<<counter[i]<<" "<<i<<endl;
	}*/
}

int swap_seats(int a, int b) {
	/*cnt++;
	if(cnt>100){
		for(int i=0;i<1;i+=0){
			
		}
	}*/
	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=1;i<8;i++){
		cout<<counter[i]<<" "<<i<<endl;
	}*/
	//for(int i=0;i<w;i++)cout<<arr[i]<<endl;
	return counter[1];
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 33 / 33
• Subtask 6: 0 / 30