Submission #395571

#	Time	Username	Problem	Language	Result	Execution time	Memory
395571		Mounir	Seats (IOI18_seats)	C++14	0 / 100	4101 ms	71620 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
using namespace std;
 
struct Extremums {
	int xMin, xMax, yMin, yMax;

	int aire(){
		return (yMax - yMin + 1) * (xMax - xMin + 1);
	}
};
 
struct Point {
	int x, y;
};
 
int nLigs, nCols, nVals;
const int MAX_VALS = (1 << 20);
const int N = MAX_VALS;
Extremums vals[2 * MAX_VALS];
bool estOk[MAX_VALS];
Point points[MAX_VALS];
 
int sum = 0;

void combine(int noeud){
	vals[noeud].xMin = min(vals[noeud * 2].xMin, vals[noeud * 2 + 1].xMin);
	vals[noeud].xMax = max(vals[noeud * 2].xMax, vals[noeud * 2 + 1].xMax);
	vals[noeud].yMin = min(vals[noeud * 2].yMin, vals[noeud * 2 + 1].yMin);
	vals[noeud].yMax = max(vals[noeud * 2].yMax, vals[noeud * 2 + 1].yMax);
}

Extremums combine(Extremums a, Extremums b){
	return {min(a.xMin, b.xMin), max(a.xMax, b.xMax), min(a.yMin, b.yMin), max(a.yMax, b.yMax)};
}

void update(int noeud){
	noeud /= 2;
	for (; noeud > 0; noeud /= 2)
		combine(noeud);
}

Extremums get(int gauche, int droite){
	if (droite < gauche) return {N, -1, N, -1};
	if (gauche%2 == 1) return combine(vals[gauche], get(gauche + 1, droite));
	if (droite%2 == 0) return combine(vals[droite], get(gauche, droite - 1));
	return get(gauche/2, droite/2);
}
 
void construire(int iVal){
	if (iVal == 0){
		vals[N] = {points[0].x, points[0].x, points[0].y, points[0].y};
		update(N + iVal);
		return;
	}
 
	vals[iVal + N] = vals[N + iVal - 1];
	chmin(vals[N + iVal].xMin, points[iVal].x);
	chmax(vals[N + iVal].xMax, points[iVal].x);
	chmin(vals[iVal + N].yMin, points[iVal].y);
	chmax(vals[iVal + N].yMax, points[iVal].y);
	sum -= estOk[iVal];
	if (vals[iVal + N].aire() == iVal + 1)
		estOk[iVal] = true;
	else
		estOk[iVal] = false;
	sum += estOk[iVal];
	update(N + iVal);
}
 
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	for (int noeud = 0; noeud < 2 * N; ++noeud)
		vals[noeud] = {N, -1, N, -1};

	nLigs = H;
	nCols = W;
	nVals = nLigs * nCols;
	for (int iVal = 0; iVal < nVals; ++iVal)
		points[iVal] = {R[iVal], C[iVal]};
 
	vals[0] = {points[0].x, points[0].x, points[0].y, points[0].y};
	estOk[0] = true; sum++;
	update(N);
	for (int iVal = 1; iVal < nVals; ++iVal)
		construire(iVal);
 
}

int getOpt(){
	sum = 0;
	int pointeur = 1;
	while (pointeur != nVals){
		Extremums nxt;
		while ((nxt = get(N, N + pointeur)).aire() != pointeur)
			pointeur = nxt.aire();
		sum++;
		pointeur++;
	}
	return sum;
}
 
int swap_seats(int a, int b) {
	swap(points[a], points[b]);

	if (abs(a - b) > 10 * 100)
		return getOpt();

	for (int iVal = min(a, b); iVal <= max(a, b); ++iVal)
		construire(iVal);
	return sum;
}

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