| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 202989 |
2020-02-18T22:13:41 Z |
hugo_pm |
Editor (BOI15_edi) |
C++17 |
|
133 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) {
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";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
5116 KB |
Output is correct |
| 2 |
Correct |
67 ms |
4984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
8172 KB |
Output is correct |
| 2 |
Correct |
74 ms |
9504 KB |
Output is correct |
| 3 |
Correct |
133 ms |
13012 KB |
Output is correct |
| 4 |
Correct |
68 ms |
4984 KB |
Output is correct |
| 5 |
Correct |
107 ms |
16228 KB |
Output is correct |
| 6 |
Correct |
57 ms |
2940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
