Submission #624691

#	Time	Username	Problem	Language	Result	Execution time	Memory
624691		moonrabbit2	Seats (IOI18_seats)	C++17	100 / 100	1452 ms	109504 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using tii=tuple<int,int,int>;
const int N=1e6+5;
int h,w,r[N],c[N],D[N];
vector<vector<int>> a;
int S[2*N];
pii pos[N],T[2*N];
pii mrg(pii A,pii B,int d){
	A.fi+=d; B.fi+=d;
	if(A.fi<B.fi) return A;
	if(A.fi>B.fi) return B;
	return pii(A.fi,A.se+B.se);
}
void init(int nd,int l,int r){
	S[nd]=0;
	if(l==r){
		T[nd]=pii(D[l],1);
		return;
	}
	int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
	init(ln,l,m); init(rn,m+1,r);
	T[nd]=mrg(T[ln],T[rn],0);
}
void add(int nd,int l,int r,int s,int e,int v){
	if(r<s||e<l) return;
	if(s<=l&&r<=e){
		S[nd]+=v;
		T[nd].fi+=v;
		return;
	}
	int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
	add(ln,l,m,s,e,v); add(rn,m+1,r,s,e,v);
	T[nd]=mrg(T[ln],T[rn],S[nd]);
}
// (r, c) 오른쪽 아래의 꼭짓점.
void Do(int r,int c,int v=0){
	// a[r][c]   a[r][c+1]
	// a[r+1][c] a[r+1][c+1]
	vector<int> X;
	for(int i=0;i<2;i++) for(int j=0;j<2;j++) X.emplace_back(a[r+i][c+j]);
	sort(X.begin(),X.end());
	if(X[0]<h*w+1){
		if(v) add(1,1,h*w,X[0],X[1]-1,v);
		else{
			D[X[0]]++;
			D[X[1]]--;
		}
	}
	if(X[2]<h*w+1){
		if(v) add(1,1,h*w,X[2],X[3]-1,v);	
		else{
			D[X[2]]++;
			D[X[3]]--;
		}
	}
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C){
	h=H;
	w=W;
	a.resize(h+2);
	for(int i=0;i<=h+1;i++) a[i].resize(w+2);
	for(int i=0;i<=h+1;i++) for(int j=0;j<=w+1;j++) a[i][j]=h*w+1;
	for(int i=0;i<h*w;i++){
		a[R[i]+1][C[i]+1]=i+1;
		r[i+1]=R[i]+1;
		c[i+1]=C[i]+1;
	}
	for(int i=0;i<=h;i++) for(int j=0;j<=w;j++) Do(i,j);
	for(int i=1;i<=h*w;i++) D[i]+=D[i-1];
	init(1,1,h*w);
}
int swap_seats(int x,int y){
	x++; y++;
	for(int i=0;i<2;i++) for(int j=0;j<2;j++) Do(r[x]-i,c[x]-j,-1);
	for(int i=0;i<2;i++) for(int j=0;j<2;j++) Do(r[y]-i,c[y]-j,-1);
	swap(a[r[x]][c[x]],a[r[y]][c[y]]);
	swap(r[x],r[y]);
	swap(c[x],c[y]);
	for(int i=0;i<2;i++) for(int j=0;j<2;j++) Do(r[x]-i,c[x]-j,1);
	for(int i=0;i<2;i++) for(int j=0;j<2;j++) Do(r[y]-i,c[y]-j,1);
	return T[1].se;
}

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