Submission #769338

#	Time	Username	Problem	Language	Result	Execution time	Memory
769338		Baytoro	Seats (IOI18_seats)	C++17	5 / 100	4070 ms	78452 KiB

seats

#include "seats.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
const int N=4e6+5;
const int INF=1e9+5;
pair<int,int> A[N];
struct node{
	int mxx, mnx, mxy,mny;
};
struct ST{
	node tree[N];
	node combine(node a, node b){
		return {max(a.mxx,b.mxx),min(a.mnx,b.mnx),max(a.mxy,b.mxy),min(a.mny,b.mny)};
	}
	void build(int x, int l, int r, vector<pair<int,int>> &vec){
		if(l==r){
			tree[x]={vec[l].fr,vec[l].fr,vec[l].sc,vec[l].sc};
			return;
		}
		int md=(l+r)/2;
		build(2*x,l,md,vec);
		build(2*x+1,md+1,r,vec);
		tree[x]=combine(tree[2*x],tree[2*x+1]);
	}
	void update(int x, int l, int r, int i, pair<int,int> val){
		if(l==r){
			tree[x]={val.fr,val.fr,val.sc,val.sc};
			return;
		}
		int md=(l+r)/2;
		if(i<=md) update(2*x  ,l   ,md,i,val);
		else      update(2*x+1,md+1,r ,i,val);
		tree[x]=combine(tree[2*x],tree[2*x+1]);
	}
	int find_minx(int x, int l, int r, int lx, int rx){
		if(l>rx || r<lx) return INF;
		if(lx<=l && r<=rx) return tree[x].mnx;
		int md=(l+r)/2;
		//cout<<l<<' '<<r<<' '<<lx<<' '<<rx<<endl;
		return min(find_minx(2*x,l,md,lx,rx),find_minx(2*x+1,md+1,r,lx,rx));
	}
	int find_maxx(int x, int l, int r, int lx, int rx){
		if(l>rx || r<lx) return -INF;
		if(lx<=l && r<=rx) return tree[x].mxx;
		int md=(l+r)/2;
		return max(find_maxx(2*x,l,md,lx,rx),find_maxx(2*x+1,md+1,r,lx,rx));
	}
	int find_miny(int x, int l, int r, int lx, int rx){
		if(l>rx || r<lx) return INF;
		if(lx<=l && r<=rx) return tree[x].mny;
		int md=(l+r)/2;
		return min(find_miny(2*x,l,md,lx,rx),find_miny(2*x+1,md+1,r,lx,rx));
	}
	int find_maxy(int x, int l, int r, int lx, int rx){
		if(l>rx || r<lx) return -INF;
		if(lx<=l && r<=rx) return tree[x].mxy;
		int md=(l+r)/2;
		return max(find_maxy(2*x,l,md,lx,rx),find_maxy(2*x+1,md+1,r,lx,rx));
	}
} st;
int k;
int h,w;
vector<int> R,C;
void give_initial_chart(int H, int W, vector<int> r, vector<int> c) {
	R=r,C=c;
	h=H,w=W;
	int n=1;
	while(n<H*W) n*=2;
	vector<pair<int,int>> v(n);
	for(int i=0;i<H*W;i++)
		v[i]={R[i],C[i]};
	k=n;
	st.build(1,0,k-1,v);
}

int swap_seats(int a, int b) {
	st.update(1,0,k-1,a,{R[b],C[b]});
	st.update(1,0,k-1,b,{R[a],C[a]});
	swap(R[a],R[b]);
	swap(C[a],C[b]);
	int id=1,ans=1;
	while(id<h*w){
		int l=st.find_minx(1,0,k-1,0,id);
		int r=st.find_maxx(1,0,k-1,0,id);
		int d=st.find_miny(1,0,k-1,0,id);
		int u=st.find_maxy(1,0,k-1,0,id);
		//cout<<R[0]<<' '<<C[0]<<endl;
		//cout<<l<<' '<<r<<' '<<d<<' '<<u<<' ';
		//cout<<id<<endl;
		if((r-l+1)*(u-d+1)-1==id) ans++,id++;
		else  id=(r-l+1)*(u-d+1)-1;
	}
	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