Submission #595180

#	Time	Username	Problem	Language	Result	Execution time	Memory
595180		FatihSolak	Seats (IOI18_seats)	C++17	5 / 100	4070 ms	108120 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
struct node{
	int l1,r1;
	int l2,r2;
	node(){
		l1 = 1e9,r1 = 0;
		l2 = 1e9,r2 = 0;
	}
	node(int a,int b,int c,int d){
		l1 = a,r1 = b;
		l2 = c,r2 = d;
	}
	int size(){
		return (r1 - l1 + 1) * (r2 - l2 + 1);
	}
};
node merge(node a,node b){
	node ret;
	ret.l1 = min(a.l1,b.l1);
	ret.r1 = max(a.r1,b.r1);

	ret.l2 = min(a.l2,b.l2);
	ret.r2 = max(a.r2,b.r2);
	return ret;
}
struct SegTree{
	vector<node> t;
	int n;
	SegTree(int size){
		n = size;
		t.assign(4*n,node());
	}
	void upd(int v,int tl,int tr,int pos,node val){
		if(tl == tr){
			t[v] = val;
			return;
		}
		int tm = (tl + tr)/2;
		if(pos <= tm){
			upd(v*2,tl,tm,pos,val);
		}
		else upd(v*2+1,tm+1,tr,pos,val);
		t[v] = merge(t[v*2],t[v*2+1]);
	}
	node get(int v,int tl,int tr,int l,int r){
		if(tr < l || r < tl)
			return node();
		if(l <= tl && tr <= r)
			return t[v];
		int tm = (tl + tr)/2;
		return merge(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
	}
	void upd(int pos,node val){
		upd(1,0,n-1,pos,val);
	}
	node get(int l,int r){
		return get(1,0,n-1,l,r);
	}
	node get(int x){
		return get(0,x);
	}
};
node v[N];
int cnt = 0;
vector<int> r,c;
SegTree tree(N);
void give_initial_chart(int h, int w, vector<int> R, vector<int> C) {
	r = R;
	c = C;
	for(int i = 0;i<h*w;i++){
		v[i] = node(r[i],r[i],c[i],c[i]);
		tree.upd(i,v[i]);
		if(tree.get(i).size() == i+1)
			cnt++; 
	}
}

int swap_seats(int a, int b) {
	if(a > b)swap(a,b);
	for(int i = a;i<=b;i++){
		if(tree.get(i).size() == i+1)
			cnt--;  
	}
	swap(v[a],v[b]);
	tree.upd(a,v[a]);
	tree.upd(b,v[b]);
	for(int i = a;i<=b;i++){
		if(tree.get(i).size() == i+1)
			cnt++; 
	}
	return cnt;
}

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