Submission #295371

#	Time	Username	Problem	Language	Result	Execution time	Memory
295371		eohomegrownapps	Seats (IOI18_seats)	C++14	17 / 100	4058 ms	56440 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> r;
vector<int> c;
vector<int> minr;
vector<int> minc;
vector<int> maxr;
vector<int> maxc;

int n;

int tot = 0;

int INF = 1e9;

void display(vector<int> &v){
	for (int i : v){
		cout<<i<<' ';
	}cout<<'\n'<<'\n';
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	r=R;
	c=C;
	n=H*W;
	minr.resize(n+1,INF);
	minc.resize(n+1,INF);
	maxr.resize(n+1,-INF);
	maxc.resize(n+1,-INF);
	for (int i = 1; i<=n; i++){
		minr[i]=min(minr[i-1],r[i-1]);
		maxr[i]=max(maxr[i-1],r[i-1]);
		minc[i]=min(minc[i-1],c[i-1]);
		maxc[i]=max(maxc[i-1],c[i-1]);
		if ((maxr[i]-minr[i]+1)*(maxc[i]-minc[i]+1)==i){
			tot++;
		}
	}
	//display(minr);display(maxr);
	//display(minc);display(maxc);
}

int swap_seats(int a, int b) {
	a++;b++;
	if (b<a){
		swap(a,b);
	}
	swap(r[a-1],r[b-1]);
	swap(c[a-1],c[b-1]);
	for (int i = a; i<=b; i++){
		if ((maxr[i]-minr[i]+1)*(maxc[i]-minc[i]+1)==i){
			tot--;
		}
		minr[i]=min(minr[i-1],r[i-1]);
		maxr[i]=max(maxr[i-1],r[i-1]);
		minc[i]=min(minc[i-1],c[i-1]);
		maxc[i]=max(maxc[i-1],c[i-1]);
		if ((maxr[i]-minr[i]+1)*(maxc[i]-minc[i]+1)==i){
			tot++;
		}
	}
	//display(minr);display(maxr);
	//display(minc);display(maxc);
  	return tot;
}

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