Submission #1090626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090626		StefanSebez	Seats (IOI18_seats)	C++14	17 / 100	4013 ms	56372 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e6+50,inf=1e9;
int n,m,res;
int X[N+50],Y[N+50],L[N+50],R[N+50],LL[N+50],RR[N+50];
void give_initial_chart(int H, int W, std::vector<int> r, std::vector<int> c) {
	int n=H,m=W;
	for(int i=1;i<=n*m;i++) X[i]=r[i-1]+1,Y[i]=c[i-1]+1;
	L[0]=LL[0]=inf;
	for(int i=1;i<=n*m;i++){
		L[i]=min(L[i-1],X[i]),R[i]=max(R[i-1],X[i]);
		LL[i]=min(LL[i-1],Y[i]),RR[i]=max(RR[i-1],Y[i]);
		if((R[i]-L[i]+1)*(RR[i]-LL[i]+1)==i) res++;
	}
}

int swap_seats(int a, int b) {
	a++,b++;
	if(a>b) swap(a,b);
	swap(X[a],X[b]),swap(Y[a],Y[b]);
    for(int i=a;i<=b;i++) if((R[i]-L[i]+1)*(RR[i]-LL[i]+1)==i) res--;
    for(int i=a;i<=b;i++){
		L[i]=min(L[i-1],X[i]),R[i]=max(R[i-1],X[i]);
		LL[i]=min(LL[i-1],Y[i]),RR[i]=max(RR[i-1],Y[i]);
		if((R[i]-L[i]+1)*(RR[i]-LL[i]+1)==i) res++;
	}
	return res;
}

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