Submission #229931

#	Time	Username	Problem	Language	Result	Execution time	Memory
229931		frodakcin	Editor (BOI15_edi)	C++11	0 / 100	6 ms	768 KiB

edi

#include <cstdio>
#include <cstring>
#include <set>
#include <functional>
#include <vector>

const int MN = 3e3+10;
int N, a[MN], b[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]&&a[b[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;
			for(j=0;~b[i][j]&&~b[b[i][j]][j];++j)
				b[i][j+1]=b[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: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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37