Submission #229942

#	Time	Username	Problem	Language	Result	Execution time	Memory
229942		frodakcin	Editor (BOI15_edi)	C++11	100 / 100	270 ms	68728 KiB

edi

#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 (stderr)

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);
                       ~~~~~^~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37