Submission #991025

#	Time	Username	Problem	Language	Result	Execution time	Memory
991025		WongChun1234	Seats (IOI18_seats)	C++14	33 / 100	1561 ms	117584 KiB

seats

#include<bits/stdc++.h>
#include "seats.h"
using namespace std;
#define lc (id<<1)
#define rc ((id<<1)|1)
#define defm int m=((l+r)>>1)
const int N=1000050;
int n,h,w,r[N],c[N];
vector<int> a[N];
struct node{
	int mn,cnt,bad,lzmn,lzbad;
}seg[N<<2];
node merge(node a,node b){
	int currmn=1e9,cnt=0;
	if (!a.bad){
		currmn=a.mn,cnt=a.cnt;
	}
	if (!b.bad){
		if (b.mn<currmn){
			currmn=b.mn,cnt=b.cnt;
		}else if (b.mn==currmn){
			cnt+=b.cnt;
		}
	}
	return {currmn,cnt,min(a.bad,b.bad),0,0};
}
void pushmn(int id,int mult){
	seg[id].lzmn+=mult;
	seg[id].mn+=mult;
}
void pushbad(int id,int mult){
	seg[id].lzbad+=mult;
	seg[id].bad+=mult;
}
void build(int id,int l,int r){
	if (l==r){
		seg[id].cnt=1;
		return;
	}
	defm;
	build(lc,l,m);
	build(rc,m+1,r);
	seg[id]=merge(seg[lc],seg[rc]);
}
void modify1(int id,int l,int r,int ql,int qr,int mult){
	if (qr<l||ql>r) return;
	if (l>=ql&&r<=qr){
		pushmn(id,mult);
		return;
	}
	defm;
	pushmn(lc,seg[id].lzmn); pushmn(rc,seg[id].lzmn);
	pushbad(lc,seg[id].lzbad); pushmn(rc,seg[id].lzbad);
	seg[id].lzmn=seg[id].lzbad=0;
	modify1(lc,l,m,ql,qr,mult);
	modify1(rc,m+1,r,ql,qr,mult);
	seg[id]=merge(seg[lc],seg[rc]);
}
void modify2(int id,int l,int r,int ql,int qr,int mult){
	if (qr<l||ql>r) return;
	if (l>=ql&&r<=qr){
		pushbad(id,mult);
		return;
	}
	defm;
	pushmn(lc,seg[id].lzmn); pushmn(rc,seg[id].lzmn);
	pushbad(lc,seg[id].lzbad); pushmn(rc,seg[id].lzbad);
	seg[id].lzmn=seg[id].lzbad=0;
	modify2(lc,l,m,ql,qr,mult);
	modify2(rc,m+1,r,ql,qr,mult);
	seg[id]=merge(seg[lc],seg[rc]);
}
void check(int x,int y,int mult){
	int srt[4]={a[x-1][y-1],a[x-1][y],a[x][y-1],a[x][y]};
	sort(srt,srt+4);
	modify1(1,0,n-1,srt[0],srt[1]-1,mult);
	modify2(1,0,n-1,srt[2],srt[3]-1,mult);
}
vector<pair<int,int>> todo;
void bigcheck(int x){
	todo.push_back({r[x],c[x]});
	todo.push_back({r[x]+1,c[x]});
	todo.push_back({r[x],c[x]+1});
	todo.push_back({r[x]+1,c[x]+1});
}
void actualcheck(int mult){
	sort(todo.begin(),todo.end());
	todo.erase(unique(todo.begin(),todo.end()),todo.end());
	for (auto i:todo){
		check(i.first,i.second,mult);
	}
	todo.clear();
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C){
	h=H,w=W,n=h*w;
	for (int i=0;i<=h+1;i++) a[i].resize(w+2);
	for (int i=0;i<n;i++) r[i]=R[i]+1,c[i]=C[i]+1;
	for (int i=0;i<=h+1;i++) for (int j=0;j<=w+1;j++) a[i][j]=1e9;
	for (int i=0;i<n;i++) a[r[i]][c[i]]=i;
	build(1,0,n-1);
	for (int i=1;i<=h+1;i++) for (int j=1;j<=w+1;j++) check(i,j,1);
	//cout<<seg[1].mn<<" "<<seg[1].cnt<<" "<<seg[1].bad<<"\n";
}
int swap_seats(int x,int y){
	bigcheck(x);
	bigcheck(y);
	actualcheck(-1);
	swap(r[x],r[y]);
	swap(c[x],c[y]);
	a[r[x]][c[x]]=x;
	a[r[y]][c[y]]=y;
	bigcheck(x);
	bigcheck(y);
	actualcheck(1);
	if (seg[1].mn==4) return seg[1].cnt;
	return 0;
}
/*int main(){
	int h,w,q,r,c;
	vector<int> rr,cc;
	cin>>h>>w>>q;
	for (int i=0;i<h*w;i++){
		cin>>r>>c;
		rr.push_back(r);
		cc.push_back(c);
	}
	init(h,w,rr,cc);
	while (q--){
		cin>>r>>c;
		cout<<swapseat(r,c)<<"\n";
	}
}*/
/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5
*/

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