Submission #139212

#	Time	Username	Problem	Language	Result	Execution time	Memory
139212		rajarshi_basu	Seats (IOI18_seats)	C++14	17 / 100	4081 ms	79932 KiB

seats

#include <bits/stdc++.h>

#include "seats.h"

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i = a;i<=b;i++)
#define ll long long int
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define ii pair<int,int>
#define il pair<int,ll>

using namespace std;

const int MAXN = 10000*100;

vi grid[MAXN];
ii id[MAXN];
int h;int w;

int l[MAXN];
int r[MAXN];
int u[MAXN];
int d[MAXN];
bool ok[MAXN];
int cnt = 0;

void update(int a,int b,bool bb = 1){
	if(bb)swap(id[a],id[b]);
	FORE(i,a,b){
		if(i == 0){
			l[i] = r[i] = id[i].ss;
			u[i] = d[i] = id[i].ff;
		}else{
			l[i] = min(l[i-1],id[i].ss);
			r[i] = max(r[i-1],id[i].ss);
			u[i] = min(u[i-1],id[i].ff);
			d[i] = max(d[i-1],id[i].ff);
		}
		cnt -= ok[i];
		ok[i] = (r[i]-l[i]+1)*(d[i]-u[i]+1) == i+1;
		cnt += ok[i];
	}
}

void give_initial_chart(int h,int w,vi r,vi c){
	::h = h;::w = w;
	
	FOR(i,h*w){
		id[i] = {r[i],c[i]};
	}
	FOR(i,h*w)ok[i] = 0;
	update(0,h*w-1,0);
	//FOR(i,h*w)cout << ok[i];cout << endl;
	//FOR(i,h*w)cout << l[i] << " " << r[i] << " " << u[i] << " " << d[i] << endl;
}

int swap_seats(int a,int b){
	update(min(a,b),max(a,b));
	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