Submission #229927

#	Time	Username	Problem	Language	Result	Execution time	Memory
229927		frodakcin	Editor (BOI15_edi)	C++11	43 / 100	1091 ms	132856 KiB

edi

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

template<class T> bool ckmax(T* a, T b){return *a<b?*a=b,1:0;}

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);
}
const int MS = 1 << 20;
std::set<int, std::greater<int>, std::allocator<int> > st[MS];
int rb[MN];
void upd(int n, int l, int r, int ql, int qr, int v)
{
	if(ql <= l && r <= qr)
		if(v<0) st[n].erase(-v);
		else st[n].insert(v);
	else
	{
		int m=l+(r-l)/2;
		if(ql<m) upd(n<<1, l, m, ql, qr, v);
		if(m<qr) upd(n<<1|1, m, r, ql, qr, v);
	}
}
int qry(int n, int l, int r, int qr)
{
	if(r <= qr)
		return st[n].empty()?-1:*st[n].begin();
	else
	{
		int m=l+(r-l)/2;
		int f=*st[n].begin();
		ckmax(&f, qry(n<<1, l, m, qr));
		if(m < qr) ckmax(&f, qry(n<<1|1, m, r, qr));
		return f;
	}
}
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])
		{
			--v;
			int k=qry(1, 0, N, b[i].t);
			if(k>*v)
			{
				upd(1, 0, N, k, rb[k], -k);
				upd(1, 0, N, k, rb[k]=b[i].t, k);
				e[k].push_back(b[i].t);
			}
			else
				e[*v].push_back(b[i].t);
		}
		else
		{
			int k = *--v;
			e[k].push_back(b[i].t);
			d[k] = d[b[i].t] = 1;
			c.erase(c.erase(v));
			upd(1, 0, N, k, rb[k]=N, k);
		}
		upd(1, 0, N, b[i].t, rb[b[i].t], -b[i].t);
	}
	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:14: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:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
edi.cpp:60: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