Submission #139208

#	Time	Username	Problem	Language	Result	Execution time	Memory
139208		rajarshi_basu	Seats (IOI18_seats)	C++14	0 / 100	334 ms	48760 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;

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){
	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(l[i-1],id[i].ff);
			d[i] = max(r[i-1],id[i].ff);
		}
		cnt -= ok[i];
		ok[i] = (r-l+1)*(d-u+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]};
	}
}

int swap_seats(int a,int b){
	update(a,b);
	return cnt;
}

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