| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 229927 |
2020-05-07T07:06:31 Z |
frodakcin |
Editor (BOI15_edi) |
C++11 |
|
1091 ms |
132856 KB |
#include <cstdio>
#include <vector>
#include <set>
#include <cassert>
#include <algorithm>
#include <functional>
template<class T> bool ckmax(T* a, T b){return *a<b?*a=b,1:0;}
struct upd
{
public:
int t, l;
bool operator < (upd o) const {return l > o.l || !(o.l > l) && t < o.t;}
};
const int MN = 3e5 + 100;
int N, a[MN], f[MN], B;
upd b[MN];
std::set<int> c, h;
bool d[MN], g[MN];
std::vector<int> e[MN];
void dfs(int n, int v)
{
f[n] = v;
for(int x:e[n])
dfs(x, v);
}
const int MS = 1 << 20;
std::set<int, std::greater<int>, std::allocator<int> > st[MS];
int rb[MN];
void upd(int n, int l, int r, int ql, int qr, int v)
{
if(ql <= l && r <= qr)
if(v<0) st[n].erase(-v);
else st[n].insert(v);
else
{
int m=l+(r-l)/2;
if(ql<m) upd(n<<1, l, m, ql, qr, v);
if(m<qr) upd(n<<1|1, m, r, ql, qr, v);
}
}
int qry(int n, int l, int r, int qr)
{
if(r <= qr)
return st[n].empty()?-1:*st[n].begin();
else
{
int m=l+(r-l)/2;
int f=*st[n].begin();
ckmax(&f, qry(n<<1, l, m, qr));
if(m < qr) ckmax(&f, qry(n<<1|1, m, r, qr));
return f;
}
}
int main(void)
{
scanf("%d", &N);
for(int i=1;i<=N;++i)
scanf("%d", a+i);
for(int i=1;i<=N;++i)
{
if(a[i]<0)
b[B++] = {i, -a[i]};
c.insert(i);
}
std::sort(b, b+B);
for(int i=0;i<B;++i)
{
//printf("B VALS: %d %d\n", b[i].t, b[i].l);
auto v = c.lower_bound(b[i].t);
assert(v != c.begin());
if(d[b[i].t])
{
--v;
int k=qry(1, 0, N, b[i].t);
if(k>*v)
{
upd(1, 0, N, k, rb[k], -k);
upd(1, 0, N, k, rb[k]=b[i].t, k);
e[k].push_back(b[i].t);
}
else
e[*v].push_back(b[i].t);
}
else
{
int k = *--v;
e[k].push_back(b[i].t);
d[k] = d[b[i].t] = 1;
c.erase(c.erase(v));
upd(1, 0, N, k, rb[k]=N, k);
}
upd(1, 0, N, b[i].t, rb[b[i].t], -b[i].t);
}
for(int i=1;i<=N;++i)
if(a[i]>=0)
dfs(i, i);
h.insert(0);
for(int i=1;i<=N;++i)
{
if(g[f[i]])
h.erase(f[i]);
else
h.insert(f[i]);
g[f[i]]^=1;
printf("%d\n", a[*std::prev(h.end())]);
}
return 0;
}
Compilation message
edi.cpp: In member function 'bool upd::operator<(upd) const':
edi.cpp:14:62: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
bool operator < (upd o) const {return l > o.l || !(o.l > l) && t < o.t;}
~~~~~~~~~~~^~~~~~~~~~
edi.cpp: In function 'int main()':
edi.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
edi.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", a+i);
~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
56696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
592 ms |
132728 KB |
Output is correct |
| 2 |
Correct |
581 ms |
132656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
377 ms |
72696 KB |
Output is correct |
| 2 |
Correct |
333 ms |
73916 KB |
Output is correct |
| 3 |
Correct |
386 ms |
76996 KB |
Output is correct |
| 4 |
Correct |
582 ms |
132856 KB |
Output is correct |
| 5 |
Correct |
1091 ms |
104568 KB |
Output is correct |
| 6 |
Correct |
495 ms |
130808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
56696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
