oj.uz

Submission #229844

# Submission time Handle Problem Language Result Execution time Memory
229844 2020-05-06T19:34:23 Z frodakcin Editor (BOI15_edi) C++11
43 / 100
 391 ms 29816 KB 
#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

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.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 29304 KB Output is correct
2 Correct 213 ms 29148 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 19704 KB Output is correct
2 Correct 156 ms 24044 KB Output is correct
3 Correct 199 ms 27256 KB Output is correct
4 Correct 215 ms 29304 KB Output is correct
5 Correct 391 ms 29816 KB Output is correct
6 Correct 185 ms 27384 KB Output is correct

Subtask #4
0 / 37.0

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