Submission #395364

#	Time	Username	Problem	Language	Result	Execution time	Memory
395364		Mounir	Seats (IOI18_seats)	C++14	0 / 100	384 ms	84984 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;

///Si ce n'est que sur une ligne.

struct Noeud {
	int mini, maxi, nBons, deb, fin;
	bool ok;
};

const int N = (1 << 20);
Noeud arbre[N * 2];
int nVals;

void combine(int noeud){
	arbre[noeud].deb = arbre[noeud * 2].deb;
	arbre[noeud].fin = arbre[noeud * 2 + 1].fin;
	arbre[noeud].mini = min(arbre[noeud * 2].mini, arbre[noeud * 2 + 1].mini);
	arbre[noeud].maxi = max(arbre[noeud * 2].maxi, arbre[noeud * 2 + 1].maxi);
	arbre[noeud].ok = (arbre[noeud].deb == arbre[noeud].mini && arbre[noeud].fin == arbre[noeud].maxi);
	arbre[noeud].nBons = arbre[noeud * 2].nBons + (arbre[noeud * 2].ok * arbre[noeud * 2 + 1].nBons);
}

int positions[N];

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	for (int noeud = 1; noeud < 2 * N; ++noeud)
		arbre[noeud] = {N + 1, - 1, 0, N + 1, N + 1};
	
	nVals = H * W;
	for (int iVal = 0; iVal < nVals; ++iVal){
		positions[iVal] = C[iVal];
		arbre[N + positions[iVal]] = {iVal, iVal, 1, positions[iVal], positions[iVal], 1};
	}

	for (int noeud = N - 1; noeud > 0; --noeud)
		combine(noeud);
}

void update(int iVal){
	int noeud = N + iVal;
	arbre[noeud] = {iVal, iVal, 1, positions[iVal], positions[iVal], 1};
	noeud /= 2;
	for (; noeud > 0; noeud /= 2)
		combine(noeud);
}

int swap_seats(int a, int b) {
	swap(positions[a], positions[b]);
	update(a);
	update(b);
	return arbre[1].nBons;
}

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