Submission #819903

#	Time	Username	Problem	Language	Result	Execution time	Memory
819903		ttamx	Seats (IOI18_seats)	C++14	31 / 100	4085 ms	72696 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;
int R[N],C[N];

struct segtree{
	struct node{
		int mnr,mxr,mnc,mxc;
		node():mnr(inf),mxr(-inf),mnc(inf),mxc(-inf){}
		node(int r,int c):mnr(r),mxr(r),mnc(c),mxc(c){}
		friend node operator+(node a,node b){
			node c;
			c.mnr=min(a.mnr,b.mnr);
			c.mxr=max(a.mxr,b.mxr);
			c.mnc=min(a.mnc,b.mnc);
			c.mxc=max(a.mxc,b.mxc);
			return c;
		}
		int calc(){
			return (mxr-mnr+1)*(mxc-mnc+1);
		}
	}t[K];
	void build(int l,int r,int i){
		if(l==r)return void(t[i]=node(R[l],C[l]));
		int m=(l+r)/2;
		build(l,m,i*2);
		build(m+1,r,i*2+1);
		t[i]=t[i*2]+t[i*2+1];
	}
	void build(){
		build(1,n,1);
	}
	void update(int l,int r,int i,int x){
		if(x<l||r<x)return;
		if(l==r)return void(t[i]=node(R[l],C[l]));
		int m=(l+r)/2;
		update(l,m,i*2,x);
		update(m+1,r,i*2+1,x);
		t[i]=t[i*2]+t[i*2+1];
	}
	void update(int x){
		update(1,n,1,x);
	}
	node query(int l,int r,int i,int x,int y){
		if(y<l||r<x)return node();
		if(x<=l&&r<=y)return t[i];
		int m=(l+r)/2;
		return query(l,m,i*2,x,y)+query(m+1,r,i*2+1,x,y);
	}
	node query(int x,int y){
		return query(1,n,1,x,y);
	}
}s;

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];
	}
	s.build();
}

int swap_seats(int a, int b){
	a++,b++;
	swap(R[a],R[b]);
	swap(C[a],C[b]);
	s.update(a);
	s.update(b);
	int idx=1,ans=0;
	while(idx<=n){
		int sz=s.query(1,idx).calc();
		if(sz==idx){
			ans++;
			idx++;
		}else{
			idx=sz;
		}
	}
	return ans;
}

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