Submission #202989

#	Time	Username	Problem	Language	Result	Execution time	Memory
202989		hugo_pm	Editor (BOI15_edi)	C++17	43 / 100	133 ms	16228 KiB

edi

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

struct Segtree
{
	vector<pii> tree; // {numéro de la requête (urgencité), niveau relatif}
	vector<int> niv;
	int sz;
	void init(vector<pii> tab, vector<int> nn)
	{
		niv = nn;
		sz = tab.size();
		tree.resize(2*sz);
		for (int i = 2*sz-1; i >= 0; --i) {
			if (i >= sz) tree[i] = tab[i-sz];
			else tree[i] = min(tree[2*i], tree[2*i+1]);
		}
	}
	void modif(int rel, int val)
	{
		rel += sz;
		tree[rel].first = val;
		while (rel > 1) {
			rel /= 2;
			tree[rel] = min(tree[2*rel], tree[2*rel+1]);
		}
	}
	int getMin(int lo, int ri)
	{
		lo += sz; ri += sz+1;
		pii res = tree[lo];
		while (lo < ri) {
			if (lo & 1) res = min(res, tree[lo++]);
			if (ri & 1) res = min(res, tree[--ri]);
			lo /= 2; ri /= 2;
		}
		if (res.first < sz) return res.second;
		else return -1;

	}
	bool isActive(int rel, int numReq)
	{
		int desacPar = -1;
		auto it = upper_bound(niv.begin(), niv.end(), rel);
		if (it != niv.end()) {
			desacPar = getMin(*it, sz-1);
		}
		if (desacPar == -1) {
			modif(rel, numReq); 
			return true;
		} else {
			modif(desacPar, sz+5);	
			return false;
		}	
	}
};

vector<int> arr;
int nbReq = 0;

int getLast()
{
	vector<pii> util;
	for (int numReq = 0; numReq < nbReq; ++numReq) {
		util.push_back({max(0, -arr[numReq]), numReq});
	}
	sort(util.begin(), util.end());
	vector<int> whereIs(nbReq);
	vector<int> niv;
	int lst = -1;
	for (int rel = 0; rel < nbReq; ++rel) {
		int numReq = util[rel].second;
		if (rel == 0 || util[rel].first != lst) {
			niv.push_back(rel);
		}
		lst = util[rel].first;

		whereIs[numReq] = rel;
		util[rel].first = nbReq+5;
		util[rel].second = rel;
	}

	Segtree arbre;
	arbre.init(util, niv);
	for (int numReq = nbReq-1; numReq >= 0; --numReq) {
		int rel = whereIs[numReq];
		bool avis = arbre.isActive(rel, numReq);
		if (arr[numReq] > 0 && avis) {
			return arr[numReq];	
		}
	}
	return 0;
}

void s1()
{
	vector<bool> act(nbReq, true);
	vector<int> dir(nbReq);
	for (int i = 0; i < nbReq; ++i) {
		if (arr[i] < 0) {
			int det = i-1;
			while (!act[det] || max(0, -arr[det]) >= -arr[i]) --det;
			dir[i] = det;
			int cur = det; act[cur] = false;
			while (!act[cur] && arr[cur] < 0) {
				cur = dir[cur];
				act[cur] = !act[cur];
			}
		}
		int ans = 0;
		for (int cib = i; cib >= 0; --cib) {
			if (act[cib] && arr[cib] > 0) {
				ans = arr[cib]; break;
			}
		}
		cout << ans << "\n";
	}
}

void s2()
{
	stack<int> pp; pp.push(0);
	for (int x : arr) {
		if (x > 0) pp.push(x);
		else pp.pop();
		cout << pp.top() << "\n";
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> nbReq;
	arr.resize(nbReq);
	bool ok1 = (nbReq <= 5000);
	bool ok2 = true;
	for (int i = 0; i < nbReq; ++i) {
		cin >> arr[i];
		ok2 &= (arr[i] >= -1);
	}
	if (ok1) s1();
	else if (ok2) s2();
	else {
		for (int i = 0; i < nbReq-1; ++i) cout << "0\n";
		cout << getLast() << "\n";
	}
}

• Subtask 1: 0 / 20
• Subtask 2: 15 / 15
• Subtask 3: 28 / 28
• Subtask 4: 0 / 37