Submission #138629

#	Time	Username	Problem	Language	Result	Execution time	Memory
138629		Arturgo	Seats (IOI18_seats)	C++14	0 / 100	3123 ms	84948 KiB

seats

#include "seats.h"
#include <algorithm>
#include <iostream>
using namespace std;

const int NB_FEUILLES = (1 << 20);
const int INFINI = NB_FEUILLES;

pair<int, int> modifs[2 * NB_FEUILLES];
int nombres[2 * NB_FEUILLES][5];

int nbLigs, nbCols;

vector<pair<int, int>> coords;
vector<vector<int>> sieges;

void update(int noeud) {
	for(int i = 0;i < 5;i++) {
		nombres[noeud][i] = 0;
	}

	if(noeud >= NB_FEUILLES) {
		if(modifs[noeud].second == 0 && modifs[noeud].first <= 4) {
			nombres[noeud][modifs[noeud].first]++;
		}
		return;
	}

	if(modifs[noeud].second == 0) {
		for(int i = 0;i < 5;i++) {
			if(i - modifs[noeud].first >= 0) {
				nombres[noeud][i] += nombres[2 * noeud][i - modifs[noeud].first];
				nombres[noeud][i] += nombres[2 * noeud + 1][i - modifs[noeud].first];
			}
		}
	}
}

int nbRectangles() {
	return nbLigs * nbCols + nombres[1][4] - NB_FEUILLES;
}

void ajoute(int deb, int fin, pair<int, int> modif, int n = 1, int d = 0, int f = NB_FEUILLES) {
	if(deb >= f || d >= fin)
		return;
	if(deb <= d && f <= fin) {
		modifs[n].first += modif.first;
		modifs[n].second += modif.second;
		update(n);
		return;
	}

	int m = (d + f) / 2;
	ajoute(deb, fin, modif, 2 * n, d, m);
	ajoute(deb, fin, modif, 2 * n + 1, m, f);
	update(n);
}

void update(int lig, int col, int sens) {
	if(lig < 0 || col < 0 || lig > nbLigs || col > nbCols)
		return;

	vector<int> vals;
	vals.push_back(sieges[lig][col]);
	vals.push_back(sieges[lig + 1][col]);
	vals.push_back(sieges[lig + 1][col + 1]);
	vals.push_back(sieges[lig][col + 1]);

	sort(vals.begin(), vals.end());

	ajoute(vals[0], vals[1], {sens, 0});
	ajoute(vals[2], vals[3], {0, sens});
}

void give_initial_chart(int _nbLigs, int _nbCols, vector<int> ligs, vector<int> cols) {
	nbLigs = _nbLigs;
	nbCols = _nbCols;
	sieges = vector<vector<int>>(nbLigs + 2, vector<int>(nbCols + 2, INFINI));
 	for(int iEleve = 0;iEleve < nbLigs * nbCols;iEleve++) {
 		coords.push_back({ligs[iEleve] + 1, cols[iEleve] + 1});
 		sieges[ligs[iEleve] + 1][cols[iEleve] + 1] = iEleve;
 	}

 	for(int iSommet = 2 * NB_FEUILLES - 1;iSommet >= 1;iSommet--) {
 		update(iSommet);
 	}

 	for(int iLig = 0;iLig < nbLigs + 2;iLig++) {
 		for(int iCol = 0;iCol < nbCols + 2;iCol++) {
 			update(iLig, iCol, 1);
 		}
 	}
}

void modify(int lig, int col, int sens) {
	update(lig - 1, col - 1, sens);
	update(lig, col - 1, sens);
	update(lig - 1, col - 1, sens);
	update(lig, col, sens);
}

int swap_seats(int a, int b) {
	modify(coords[a].first, coords[a].second, -1);
	modify(coords[b].first, coords[b].second, -1);

	swap(sieges[coords[a].first][coords[a].second], sieges[coords[b].first][coords[b].second]);
	swap(coords[a], coords[b]);

	modify(coords[a].first, coords[a].second, 1);
	modify(coords[b].first, coords[b].second, 1);

  	return nbRectangles();
}

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