Submission #229844

#	Time	Username	Problem	Language	Result	Execution time	Memory
229844		frodakcin	Editor (BOI15_edi)	C++11	43 / 100	391 ms	29816 KiB

edi

#include <cstdio>
#include <vector>
#include <set>
#include <cassert>
#include <algorithm>

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);
}
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])
			e[*--v].push_back(b[i].t);
		else
		{
			e[*--v].push_back(b[i].t);
			d[*v] = d[b[i].t] = 1;
			c.erase(c.erase(v));
		}
	}
	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 (stderr)

edi.cpp: In member function 'bool upd::operator<(upd) const':
edi.cpp:11: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:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
edi.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a+i);
   ~~~~~^~~~~~~~~~~

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