# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
229942 |
2020-05-07T07:45:38 Z |
frodakcin |
Editor (BOI15_edi) |
C++11 |
|
270 ms |
68728 KB |
#include <cstdio>
#include <cstring>
#include <set>
#include <functional>
#include <vector>
#include <algorithm>
const int MN = 3e5+10;
int N, a[MN], b[MN][20], g[MN][20], d[MN];
bool e[MN];
std::set<int, std::greater<int>, std::allocator<int> > f;
std::vector<int> c[MN];
void dfs(int n, int v)
{
d[n]=v;
for(int x:c[n])
dfs(x, v);
}
int main(void)
{
scanf("%d", &N);
for(int i=0;i<N;++i) scanf("%d", a+i);
memset(b, -1, sizeof b);
for(int i=0,j,x;i<N;++i)
{
if(a[i]<0)
{
j=0, x=i-1;
for(;~b[x][j];++j);
for(--j;j>=0;--j)
if(~b[x][j]&&g[x][j] <= a[i])
x=b[x][j];
//printf("%d -> %d\n", i, x);
c[x].push_back(i);
b[i][0] = x-1, g[i][0]=a[i];
for(j=0;~b[i][j]&&~b[b[i][j]][j];++j)
b[i][j+1]=b[b[i][j]][j], g[i][j+1] = std::max(g[i][j], g[b[i][j]][j]);
}
}
for(int i=0;i<N;++i)
if(a[i]>=0)
dfs(i, i);
for(int i=0;i<N;++i)
{
if(e[d[i]])
f.erase(d[i]);
else
f.insert(d[i]);
e[d[i]]^=1;
if(f.empty())
printf("0\n");
else
printf("%d\n", a[*f.begin()]);
}
return 0;
}
Compilation message
edi.cpp: In function 'int main()':
edi.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
edi.cpp:22:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0;i<N;++i) scanf("%d", a+i);
~~~~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
30848 KB |
Output is correct |
2 |
Correct |
22 ms |
31232 KB |
Output is correct |
3 |
Correct |
22 ms |
30848 KB |
Output is correct |
4 |
Correct |
21 ms |
30848 KB |
Output is correct |
5 |
Correct |
22 ms |
31488 KB |
Output is correct |
6 |
Correct |
21 ms |
30848 KB |
Output is correct |
7 |
Correct |
23 ms |
31464 KB |
Output is correct |
8 |
Correct |
21 ms |
30848 KB |
Output is correct |
9 |
Correct |
23 ms |
31488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
146 ms |
63608 KB |
Output is correct |
2 |
Correct |
142 ms |
63608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
97 ms |
43896 KB |
Output is correct |
2 |
Correct |
115 ms |
48380 KB |
Output is correct |
3 |
Correct |
205 ms |
59512 KB |
Output is correct |
4 |
Correct |
144 ms |
63736 KB |
Output is correct |
5 |
Correct |
183 ms |
66680 KB |
Output is correct |
6 |
Correct |
132 ms |
62328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
30848 KB |
Output is correct |
2 |
Correct |
22 ms |
31232 KB |
Output is correct |
3 |
Correct |
22 ms |
30848 KB |
Output is correct |
4 |
Correct |
21 ms |
30848 KB |
Output is correct |
5 |
Correct |
22 ms |
31488 KB |
Output is correct |
6 |
Correct |
21 ms |
30848 KB |
Output is correct |
7 |
Correct |
23 ms |
31464 KB |
Output is correct |
8 |
Correct |
21 ms |
30848 KB |
Output is correct |
9 |
Correct |
23 ms |
31488 KB |
Output is correct |
10 |
Correct |
146 ms |
63608 KB |
Output is correct |
11 |
Correct |
142 ms |
63608 KB |
Output is correct |
12 |
Correct |
97 ms |
43896 KB |
Output is correct |
13 |
Correct |
115 ms |
48380 KB |
Output is correct |
14 |
Correct |
205 ms |
59512 KB |
Output is correct |
15 |
Correct |
144 ms |
63736 KB |
Output is correct |
16 |
Correct |
183 ms |
66680 KB |
Output is correct |
17 |
Correct |
132 ms |
62328 KB |
Output is correct |
18 |
Correct |
185 ms |
59000 KB |
Output is correct |
19 |
Correct |
182 ms |
62200 KB |
Output is correct |
20 |
Correct |
270 ms |
68728 KB |
Output is correct |
21 |
Correct |
147 ms |
65272 KB |
Output is correct |
22 |
Correct |
176 ms |
68728 KB |
Output is correct |