제출 #819894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
819894		ttamx	자리 배치 (IOI18_seats)	C++14	5 / 100	4075 ms	56928 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> p2;

const int N=1e6+5;
const int K=(1<<21)+5;
const int inf=1e9;

int h,w,n;
vector<int> r(N),c(N);

struct minsegtree{
	int t[K];
	void build(int l,int r,int i,vector<int> &a){
		if(l==r)return void(t[i]=a[l]);
		int m=(l+r)/2;
		build(l,m,i*2,a);
		build(m+1,r,i*2+1,a);
		t[i]=min(t[i*2],t[i*2+1]);
	}
	void build(vector<int> &a){
		build(1,n,1,a);
	}
	void update(int l,int r,int i,int x,int v){
		if(x<l||r<x)return;
		if(l==r)return void(t[i]=v);
		int m=(l+r)/2;
		update(l,m,i*2,x,v);
		update(m+1,r,i*2+1,x,v);
		t[i]=min(t[i*2],t[i*2+1]);
	}
	void update(int x,int v){
		update(1,n,1,x,v);
	}
	int query(int l,int r,int i,int x,int y){
		if(y<l||r<x)return inf;
		if(x<=l&&r<=y)return t[i];
		int m=(l+r)/2;
		return min(query(l,m,i*2,x,y),query(m+1,r,i*2+1,x,y));
	}
	int query(int x,int y){
		return query(1,n,1,x,y);
	}
}mnr,mnc;

struct maxsegtree{
	int t[K];
	void build(int l,int r,int i,vector<int> &a){
		if(l==r)return void(t[i]=a[l]);
		int m=(l+r)/2;
		build(l,m,i*2,a);
		build(m+1,r,i*2+1,a);
		t[i]=max(t[i*2],t[i*2+1]);
	}
	void build(vector<int> &a){
		build(1,n,1,a);
	}
	void update(int l,int r,int i,int x,int v){
		if(x<l||r<x)return;
		if(l==r)return void(t[i]=v);
		int m=(l+r)/2;
		update(l,m,i*2,x,v);
		update(m+1,r,i*2+1,x,v);
		t[i]=max(t[i*2],t[i*2+1]);
	}
	void update(int x,int v){
		update(1,n,1,x,v);
	}
	int query(int l,int r,int i,int x,int y){
		if(y<l||r<x)return -inf;
		if(x<=l&&r<=y)return t[i];
		int m=(l+r)/2;
		return max(query(l,m,i*2,x,y),query(m+1,r,i*2+1,x,y));
	}
	int query(int x,int y){
		return query(1,n,1,x,y);
	}
}mxr,mxc;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
	h=H,w=W;
	n=h*w;
	for(int i=1;i<=n;i++){
		r[i]=R[i-1];
		c[i]=C[i-1];
	}
	mnr.build(r);
	mxr.build(r);
	mnc.build(c);
	mxc.build(c);
}

int swap_seats(int a, int b){
	a++,b++;
	swap(r[a],r[b]);
	swap(c[a],c[b]);
	mnr.update(a,r[a]);
	mnr.update(b,r[b]);
	mnc.update(a,c[a]);
	mnc.update(b,c[b]);
	mxr.update(a,r[a]);
	mxr.update(b,r[b]);
	mxc.update(a,c[a]);
	mxc.update(b,c[b]);
	int idx=1,ans=0;
	while(idx<=n){
		int sz=(mxr.query(1,idx)-mnr.query(1,idx)+1)*(mxc.query(1,idx)-mnc.query(1,idx)+1);
		if(sz==idx){
			ans++;
			idx++;
		}else{
			idx=sz;
		}
	}
	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