oj.uz

Submission #229939

# Submission time Handle Problem Language Result Execution time Memory
229939 2020-05-07T07:36:41 Z frodakcin Editor (BOI15_edi) C++11
0 / 100
 165 ms 65400 KB 
#include <cstdio>
#include <cstring>
#include <set>
#include <functional>
#include <vector>

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&&~b[x][j]&&g[x][j] <= a[i];--j)
				x=b[x][j];
			if(a[x] <= a[i])
				x=b[x][0];
			//printf("%d -> %d\n", i, x);
			c[x].push_back(i);
			b[i][0] = x-1, g[i][0]=a[x-1];
			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:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
edi.cpp:21: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);
                       ~~~~~^~~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 30848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 65400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 107 ms 44408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 30848 KB Output isn't correct
2 Halted 0 ms 0 KB -