제출 #421755

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
421755		alishahali1382	자리 배치 (IOI18_seats)	C++14	0 / 100	1141 ms	238708 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
#pragma GCC optimize ("O2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, pii> pi4;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto dcba:abcd) cerr<<dcba<<", "; cerr<<"\n";}
#define pb push_back
#define SZ(x) ((int)x.size())
#define all(x) x.begin(), x.end()

const int inf=1000001000; // 1e9
const ll INF=10000000010000000ll; // 1e16
const int mod=1000000007;
const int MAXN=1000010, LOG=18;

pi4 combine(pi4 a, pi4 b){ return {{min(a.first.first, b.first.first), min(a.first.second, b.first.second)}, {max(a.second.first, b.second.first), max(a.second.second, b.second.second)}};}

int n, m, k, H, W, x, y, t, ans;
int ok[MAXN];
pii A[MAXN];
vector<vi> G;

struct Segment{
	pi4 seg[MAXN<<1];
	Segment(){
		fill(seg, seg+MAXN*2, pi4(pii(inf, inf), pii(-1, -1)));
	}
	void Set(int pos, pi4 x){
		for (seg[pos+=MAXN]=x; pos>1; pos>>=1) seg[pos>>1]=combine(seg[pos], seg[pos^1]);
	}
	pi4 Get(int l, int r){
		pi4 res=seg[0];
		for (l+=MAXN, r+=MAXN; l<r; l>>=1, r>>=1){
			if (l&1) res=combine(res, seg[l++]);
			if (r&1) res=combine(res, seg[--r]);
		}
		return res;
	}
} seg, seg1, seg2;

int getS(pi4 x){
	return (x.second.first-x.first.first+1)*(x.second.second-x.first.second+1);
}
void give_initial_chart(int _H, int _W, vi R, vi C) {
	H=_H;
	W=_W;
	G.resize(H+2);
	for (int i=0; i<=H+1; i++) G[i].resize(H+2, 0);
	n=H*W;
	for (int i=0; i<n; i++){
		A[i]={R[i], C[i]};
		ans+=(ok[i]=(getS(seg.seg[1])==i+1));
		seg.Set(i, {A[i], A[i]});
		seg1.Set(A[i].first*W+A[i].second, {A[i], A[i]});
		seg2.Set(A[i].first+A[i].second*H, {A[i], A[i]});
	}
}
int swap_seats(int a, int b){
	if (a>b) swap(a, b);
	swap(A[a], A[b]);
	seg.Set(a, {A[a], A[a]});
	seg.Set(b, {A[b], A[b]});
	seg1.Set(A[a].first*W+A[a].second, {A[a], A[a]});
	seg2.Set(A[a].first+A[a].second*H, {A[a], A[a]});
	seg1.Set(A[b].first*W+A[b].second, {A[b], A[b]});
	seg2.Set(A[b].first+A[b].second*H, {A[b], A[b]});
	
	ans=1;
	pi4 curr={A[0], A[0]};
	int shit=0;
	while (getS(curr)!=n){
		int mx=getS(curr);
		pi4 nxt=combine(curr, pi4(A[mx], A[mx]));
		assert(shit++<=4000);
		while (curr!=nxt){
			// assert(shit++<=4000);
			if (nxt.first.first<curr.first.first){
				curr.first.first--;
				nxt=combine(nxt, seg1.Get(curr.first.first*W+curr.first.second, curr.first.first*W+curr.second.second+1));
			}
			if (nxt.second.first>curr.second.first){
				curr.second.first++;
				nxt=combine(nxt, seg1.Get(curr.second.first*W+curr.first.second, curr.second.first*W+curr.second.second+1));
			}
			if (nxt.first.second<curr.first.second){
				curr.first.second--;
				nxt=combine(nxt, seg2.Get(curr.first.first+curr.first.second*H, curr.second.first+curr.first.second*H+1));
			}
			if (nxt.second.second>curr.second.second){
				curr.second.second++;
				nxt=combine(nxt, seg2.Get(curr.first.first+curr.second.second*H, curr.second.first+curr.second.second*H+1));
			}
		}
		ans++;
	}
	return ans;
}
/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5

2 3 1
1 2
1 0
1 1
0 1
0 2
0 0
0 5

*/

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