Submission #395581

#	Time	Username	Problem	Language	Result	Execution time	Memory
395581		Mounir	Seats (IOI18_seats)	C++14	31 / 100	4094 ms	73576 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);
	}

	void debug(){
		;//cout << xMin << " " << xMax << " " << yMin << " " << yMax << endl;
	}
};
 
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);
/*
	if (noeud == 524288){
		cout << "wsh wsh\n";
		vals[noeud * 2].debug();
		vals[noeud * 2 + 1].debug();
		cout << "----\n";
	}*/
}

Extremums combiner(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){
	//cout << "get " << gauche << " " << droite << endl;

	if (droite < gauche) return {N, -1, N, -1};
	if (gauche%2 == 1) return combiner(vals[gauche], get(gauche + 1, droite));
	if (droite%2 == 0) return combiner(vals[droite], get(gauche, droite - 1));
	return get(gauche/2, droite/2);
}
 
void construire(int iVal){
	vals[N + iVal] = {points[iVal].x, points[iVal].x, points[iVal].y, points[iVal].y};
	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]};

	for (int iVal = 0; iVal < nVals; ++iVal)
		construire(iVal);
 
}

int getOpt(){
	sum = 0;
	int pointeur = 0;
	//cout << "REQ\n";
	int noeud = 524288;
	vals[noeud].debug();

	while (pointeur < nVals){
		Extremums nxt;
		while ((nxt = get(N, N + pointeur)).aire() != pointeur + 1){
			//cout << "boucle " << pointeur << " " << nxt.aire() << endl;
			//cout << nxt.xMin << " " << nxt.xMax << " " << nxt.yMin << " " << nxt.yMax << endl << endl;
			pointeur = nxt.aire() - 1;
		}
		sum++;
		//cout << "jsp " << pointeur << endl;
		//Extremums a = nxt;
		//cout << a.xMin << " " << a.xMax << " " << a.yMin << " " << a.yMax << " " << a.aire() << endl;
		pointeur++;

	}
	return sum;
}
 
int swap_seats(int a, int b) {
	swap(points[a], points[b]);
	vals[N + a] = {points[a].x, points[a].x, points[a].y, points[a].y};
	vals[N + b] = {points[b].x, points[b].x, points[b].y, points[b].y};
	update(N + a);
	update(N + b);

	if (true)
		return getOpt();

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

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