Submission #139780

#	Time	Username	Problem	Language	Result	Execution time	Memory
139780		almogwald	Seats (IOI18_seats)	C++14	17 / 100	4100 ms	45472 KiB

seats

#include <utility>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#include <iostream>

#include "seats.h"
#define fori(i,n) for(int i=0;i<n;i++)
#define forn(i,n) for(int i=1;i<n;i++)
#define forib(i,n) for(int i=n-1;i>=0;i--)
#define fornb(i,n) for(int i=n-1;i>0;i--)
#define maxl 10000000000
#define con continue;
typedef long long lol;
using namespace std;
typedef vector<int> veci;
typedef pair<lol,lol> point;
lol sum=1;

vector<int> r,c;
vector<int> mar,mac;
vector<int> mir,mic;
vector<veci> all;
veci minr,minc;
int h,w;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	r = R;
	c = C;
	h=H;
	w=W;
	mir.push_back(r[0]);
	mar.push_back(r[0]);
	mic.push_back(c[0]);
	mac.push_back(c[0]);
	forn(i,h*w){
		mir.push_back(min(r[i],mir[i-1]));
		mar.push_back(max(r[i],mar[i-1]));
		mic.push_back(min(c[i],mic[i-1]));
		mac.push_back(max(c[i],mac[i-1]));
		if((mar[i]-mir[i]+1)*(mac[i]-mic[i]+1)==i+1){
			sum++;
		}
	}
}

int swap_seats(int a, int b) {
	if(a>b){
		swap(a,b);
	}
	swap(c[a],c[b]);
	swap(r[a],r[b]);
	if(a==0){
		mir[0]=r[0];
		mar[0]=r[0];
		mic[0]=c[0];
		mac[0]=c[0];
		a++;
	}
	for(int i=a;i<b;i++){
		if((mar[i]-mir[i]+1)*(mac[i]-mic[i]+1)==i+1){
			sum--;
		}
	}
	for(int i=a;i<b;i++){
		mir[i]=min(r[i],mir[i-1]);
		mic[i]=min(c[i],mic[i-1]);
		mar[i]=max(r[i],mar[i-1]);
		mac[i]=max(c[i],mac[i-1]);
		if((mar[i]-mir[i]+1)*(mac[i]-mic[i]+1)==i+1){
			sum++;
		}
	}
	return sum;
}

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