Submission #817209

#	Time	Username	Problem	Language	Result	Execution time	Memory
817209		Dan4Life	Seats (IOI18_seats)	C++17	17 / 100	4058 ms	56636 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
using vi = vector<int>;
const int MX = (int)1e6+10;
vi r, c;

bool a[MX];
int n, m, ans;
int rMin[MX], rMax[MX], cMin[MX], cMax[MX];

void give_initial_chart(int H, int W, vi R, vi C) {
	n = H, m = W; r = R; c = C;
	for(int i = 0; i < n*m; i++){
		rMin[i] = (i?min(rMin[i-1],r[i]):r[i]);
		rMax[i] = (i?max(rMax[i-1],r[i]):r[i]);
		cMin[i] = (i?min(cMin[i-1],c[i]):c[i]);
		cMax[i] = (i?max(cMax[i-1],c[i]):c[i]);
		a[i] = ((i+1)==(rMax[i]-rMin[i]+1)*(cMax[i]-cMin[i]+1));
		ans+=a[i];
	}
}

int swap_seats(int x, int y) {
	if(x>y) swap(x,y);
	swap(r[x],r[y]); swap(c[x],c[y]);
	for(int i = x; i <= y; i++){
		ans-=a[i];
		rMin[i] = (i?min(rMin[i-1],r[i]):r[i]);
		rMax[i] = (i?max(rMax[i-1],r[i]):r[i]);
		cMin[i] = (i?min(cMin[i-1],c[i]):c[i]);
		cMax[i] = (i?max(cMax[i-1],c[i]):c[i]);
		a[i] = ((i+1)==(rMax[i]-rMin[i]+1)*(cMax[i]-cMin[i]+1));
		ans+=a[i];
	} 
	return ans;
}

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