#ifndef LOCAL
#pragma GCC optimize ("O3")
#endif
#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return {i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (c it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(x...) " [" #x ": " << (x) << "] "
using ld = long double;
using ll = long long;
constexpr int mod = 1000 * 1000 * 1000 + 7;
constexpr int odw2 = (mod + 1) / 2;
void OdejmijOd(int& a, int b) { a -= b; if (a < 0) a += mod; }
int Odejmij(int a, int b) { OdejmijOd(a, b); return a; }
void DodajDo(int& a, int b) { a += b; if (a >= mod) a -= mod; }
int Dodaj(int a, int b) { DodajDo(a, b); return a; }
int Mnoz(int a, int b) { return (ll) a * b % mod; }
void MnozDo(int& a, int b) { a = Mnoz(a, b); }
int Pot(int a, int b) { int res = 1; while (b) { if (b % 2 == 1) MnozDo(res, a); a = Mnoz(a, a); b /= 2; } return res; }
int Odw(int a) { return Pot(a, mod - 2); }
void PodzielDo(int& a, int b) { MnozDo(a, Odw(b)); }
int Podziel(int a, int b) { return Mnoz(a, Odw(b)); }
int Moduluj(ll x) { x %= mod; if (x < 0) x += mod; return x; }
template <typename T> T Maxi(T& a, T b) { return a = max(a, b); }
template <typename T> T Mini(T& a, T b) { return a = min(a, b); }
constexpr int nax = 300 * 1000 + 105;
set<int> on_level[nax];
int n2;
int drz[nax * 4];
void Init(int n) {
n2 = 1;
while (n2 <= n) n2 *= 2;
for (int i = 1; i < n2 * 2; i++) {
drz[i] = numeric_limits<int>::min();
}
}
void Update(int w) {
w += n2;
if (on_level[w - n2].empty()) drz[w] = numeric_limits<int>::min();
else drz[w] = *on_level[w - n2].rbegin();
w /= 2;
while (w) {
drz[w] = max(drz[w * 2], drz[w * 2 + 1]);
w /= 2;
}
}
void Sksoruj(int lev, int pos) {
auto it = on_level[lev].find(pos);
if (it == on_level[lev].end()) {
on_level[lev].insert(pos);
} else {
on_level[lev].erase(it);
}
Update(lev);
}
int Daj(int lev) {
int a = n2;
int b = n2 + lev - 1;
int wyn = max(drz[a], drz[b]);
while ((a / 2) != (b / 2)) {
if (a % 2 == 0) Maxi(wyn, drz[a + 1]);
if (b % 2 == 1) Maxi(wyn, drz[b - 1]);
a /= 2;
b /= 2;
}
return wyn;
}
//set<pair<int, int>> active;
//
//void Sksoruj(int lev, int pos) {
// auto it2 = active.find(make_pair(lev, pos));
// if (it2 == active.end()) {
// active.insert(make_pair(lev, pos));
// } else {
// active.erase(it2);
// }
//}
//
//int Daj(int lev) {
// auto it = active.end();
// for (auto it2 = active.begin(); it2 != active.end(); ++it2) {
// if (it2->first < lev) {
// if (it == active.end() or it->second < it2->second) {
// it = it2;
// }
// }
// }
// assert(it != active.end());
// return it->second;
//}
int level[nax];
int type[nax];
int ojc[nax];
int root[nax];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
Init(n);
for (int i = 1; i <= n; i++) {
cin >> type[i];
if (type[i] < 0) {
level[i] = -type[i];
ojc[i] = Daj(level[i]);
root[i] = root[ojc[i]];
debug() << imie(i) imie(ojc[i]) imie(root[i]);
int j = i;
while (true) {
Sksoruj(level[j], j);
if (j == ojc[j]) break;
j = ojc[j];
}
} else {
assert(type[i] > 0);
level[i] = 0;
root[i] = i;
ojc[i] = i;
Sksoruj(level[i], i);
//active.insert(make_pair(level[i], i));
}
const int pos = Daj(1);
if (pos == numeric_limits<int>::min()) {
cout << 0 << '\n';
} else {
cout << type[pos] << '\n';
}
// debug() << imie(active);
// auto it = active.lower_bound(make_pair(1, numeric_limits<int>::min()));
// if (it == active.begin()) {
// cout << 0 << '\n';
// } else {
// --it;
// cout << type[it->second] << '\n';
// }
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
14456 KB |
Output is correct |
| 2 |
Correct |
17 ms |
14820 KB |
Output is correct |
| 3 |
Correct |
13 ms |
14820 KB |
Output is correct |
| 4 |
Correct |
14 ms |
14820 KB |
Output is correct |
| 5 |
Correct |
259 ms |
14820 KB |
Output is correct |
| 6 |
Correct |
13 ms |
14820 KB |
Output is correct |
| 7 |
Correct |
15 ms |
14820 KB |
Output is correct |
| 8 |
Correct |
15 ms |
14820 KB |
Output is correct |
| 9 |
Correct |
16 ms |
14948 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
214 ms |
33452 KB |
Output is correct |
| 2 |
Correct |
184 ms |
34952 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
202 ms |
34952 KB |
Output is correct |
| 2 |
Execution timed out |
3059 ms |
34952 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
14456 KB |
Output is correct |
| 2 |
Correct |
17 ms |
14820 KB |
Output is correct |
| 3 |
Correct |
13 ms |
14820 KB |
Output is correct |
| 4 |
Correct |
14 ms |
14820 KB |
Output is correct |
| 5 |
Correct |
259 ms |
14820 KB |
Output is correct |
| 6 |
Correct |
13 ms |
14820 KB |
Output is correct |
| 7 |
Correct |
15 ms |
14820 KB |
Output is correct |
| 8 |
Correct |
15 ms |
14820 KB |
Output is correct |
| 9 |
Correct |
16 ms |
14948 KB |
Output is correct |
| 10 |
Correct |
214 ms |
33452 KB |
Output is correct |
| 11 |
Correct |
184 ms |
34952 KB |
Output is correct |
| 12 |
Correct |
202 ms |
34952 KB |
Output is correct |
| 13 |
Execution timed out |
3059 ms |
34952 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
