Submission #819886

#	Time	Username	Problem	Language	Result	Execution time	Memory
819886		ttamx	Seats (IOI18_seats)	C++14	5 / 100	4057 ms	73804 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>

using namespace std;

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 minsegtree{
	int t[K];
	void update(int l,int r,int i,int x,int v){
		if(x<l||r<x)return;
		if(l==r)return void(t[i]=v);
		int m=(l+r)/2;
		update(l,m,i*2,x,v);
		update(m+1,r,i*2+1,x,v);
		t[i]=min(t[i*2],t[i*2+1]);
	}
	void update(int x,int v){
		update(1,n,1,x,v);
	}
	int query(int l,int r,int i,int x,int y){
		if(y<l||r<x)return inf;
		if(x<=l&&r<=y)return t[i];
		int m=(l+r)/2;
		return min(query(l,m,i*2,x,y),query(m+1,r,i*2+1,x,y));
	}
	int query(int x,int y){
		return query(1,n,1,x,y);
	}
}mnr,mnc;

struct maxsegtree{
	int t[K];
	void update(int l,int r,int i,int x,int v){
		if(x<l||r<x)return;
		if(l==r)return void(t[i]=v);
		int m=(l+r)/2;
		update(l,m,i*2,x,v);
		update(m+1,r,i*2+1,x,v);
		t[i]=max(t[i*2],t[i*2+1]);
	}
	void update(int x,int v){
		update(1,n,1,x,v);
	}
	int query(int l,int r,int i,int x,int y){
		if(y<l||r<x)return -inf;
		if(x<=l&&r<=y)return t[i];
		int m=(l+r)/2;
		return max(query(l,m,i*2,x,y),query(m+1,r,i*2+1,x,y));
	}
	int query(int x,int y){
		return query(1,n,1,x,y);
	}
}mxr,mxc;

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];
		mnr.update(i,r[i]);
		mxr.update(i,r[i]);
		mnc.update(i,c[i]);
		mxc.update(i,c[i]);
	}
}

int swap_seats(int a, int b){
	a++,b++;
	swap(r[a],r[b]);
	swap(c[a],c[b]);
	mnr.update(a,r[a]);
	mnr.update(b,r[b]);
	mnc.update(a,c[a]);
	mnc.update(b,c[b]);
	mxr.update(a,r[a]);
	mxr.update(b,r[b]);
	mxc.update(a,c[a]);
	mxc.update(b,c[b]);
	int idx=1,ans=0;
	while(idx<=n){
		int sz=(mxr.query(1,idx)-mnr.query(1,idx)+1)*(mxc.query(1,idx)-mnc.query(1,idx)+1);
		if(sz==idx){
			ans++;
			idx++;
		}else{
			idx=sz;
		}
	}
	cerr << "\n";
	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