Submission #595131

#	Time	Username	Problem	Language	Result	Execution time	Memory
595131		FatihSolak	Seats (IOI18_seats)	C++17	17 / 100	4067 ms	53544 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
struct node{
	int l1 = 1e9,r1 = 0;
	int l2 = 1e9,r2 = 0;
	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;
}
node v[N];
int cnt = 0;
vector<int> r,c;
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] = {r[i],r[i],c[i],c[i]};
		if(i)
			v[i] = merge(v[i],v[i-1]);
		if(v[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(v[i].size() == i+1)
			cnt--; 
	}
	swap(r[a],r[b]);
	swap(c[a],c[b]);
	for(int i = a;i<=b;i++){
		v[i] = {r[i],r[i],c[i],c[i]};
		if(i)
			v[i] = merge(v[i],v[i-1]);
		if(v[i].size() == i+1)
			cnt++; 
	}
	return cnt;
}

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