oj.uz

Submission #202993

# Submission time Handle Problem Language Result Execution time Memory
202993 2020-02-18T22:22:15 Z hugo_pm Editor (BOI15_edi) C++17
63 / 100
 144 ms 16228 KB 
#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) {
		int cur = i;
		while (arr[cur] < 0) {
			act[cur] = true;
			int det = cur-1;
			while (!act[det] || max(0, -arr[det]) >= -arr[cur]) --det;
			dir[cur] = det;
			act[det] = false;
			if (arr[det] < 0) { cur = dir[det]; act[cur] = true; }
			else break;
		}
		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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 19 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 45 ms 376 KB Output is correct
6 Correct 6 ms 300 KB Output is correct
7 Correct 7 ms 504 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 6 ms 380 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 3576 KB Output is correct
2 Correct 64 ms 3576 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 7276 KB Output is correct
2 Correct 82 ms 8428 KB Output is correct
3 Correct 126 ms 11372 KB Output is correct
4 Correct 66 ms 3576 KB Output is correct
5 Correct 92 ms 14156 KB Output is correct
6 Correct 57 ms 2168 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 19 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 45 ms 376 KB Output is correct
6 Correct 6 ms 300 KB Output is correct
7 Correct 7 ms 504 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 6 ms 380 KB Output is correct
10 Correct 68 ms 3576 KB Output is correct
11 Correct 64 ms 3576 KB Output is correct
12 Correct 75 ms 7276 KB Output is correct
13 Correct 82 ms 8428 KB Output is correct
14 Correct 126 ms 11372 KB Output is correct
15 Correct 66 ms 3576 KB Output is correct
16 Correct 92 ms 14156 KB Output is correct
17 Correct 57 ms 2168 KB Output is correct
18 Incorrect 144 ms 16228 KB Output isn't correct
19 Halted 0 ms 0 KB -