oj.uz

Submission #467996

# Submission time Handle Problem Language Result Execution time Memory
467996 2021-08-25T20:16:30 Z blue Comparing Plants (IOI20_plants) C++17
44 / 100
 2751 ms 68660 KB 
#include "plants.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int N;
int K;

const long long INF = 1e9;

struct segtree
{
	int l;
	int r;

	pair<long long, int> mn; //min first, index second
	pair<long long, int> mx; //max first, index second
	int lp = 0;

	segtree* left = NULL;
	segtree* right = NULL;

	segtree()
	{
		;
	}

	segtree(int L, int R)
	{
		l = L;
		r = R;

		mn = make_pair(0, l);
		mx = make_pair(0, l);

		if(l == r) return;

		int m = (l+r)/2;

		left = new segtree(l, m);
		right = new segtree(m+1, r);
	}

	void add(int L, int R, long long V)
	{
		L = (L + 10*N) % N;
		R = (R + 10*N) % N;


		if(R < L)
		{
			add(L, N-1, V);
			add(0, R, V);
			return;
		}

		if(R < l || r < L) return;
		else if(L <= l && r <= R)
		{
			lp += V;
			mn.first += V;
			mx.first += V;
		}
		else
		{
			left->add(L, R, V);
			right->add(L, R, V);

			mn = min(left->mn, right->mn);
			mn.first += lp;

			mx = max(left->mx, right->mx);
			mx.first += lp;
		}
	}

	pair<long long, int> rangemin(int L, int R)
	{
		L = (L + 10*N) % N;
		R = (R + 10*N) % N;

		if(R < L)
		{
			return min(rangemin(L, N-1), rangemin(0, R));
		}

		if(R < l || r < L) return make_pair(+2*INF, -1);
		else if(L <= l && r <= R)
		{
			return mn;
		}
		else
		{
			pair<long long, int> A = min(left->rangemin(L, R), right->rangemin(L, R));
			A.first += lp;
			return A;
		}
	}

	pair<long long, int> rangemax(int L, int R)
	{
		L = (L + 10*N) % N;
		R = (R + 10*N) % N;

		if(R < L)
		{
			return max(rangemax(L, N-1), rangemax(0, R));
		}

		if(R < l || r < L) return make_pair(-2*INF, -1);
		else if(L <= l && r <= R)
		{
			return mx;
		}
		else
		{
			pair<long long, int> A = max(left->rangemax(L, R), right->rangemax(L, R));
			A.first += lp;
			// cerr << "returning " << A.first << ' ' << A.second << " for rangemax " << L << ' ' << R << '\n';
			return A;
		}
	}
};

segtree R;
vector<int> pos;


void init(int k, vector<int> r)
{
	N = r.size();
	K = k;


	segtree R(0, N-1);

	segtree S(0, N-1);

	vector<int> h;

	for(int i = 0; i < N; i++)
	{
		R.add(i, i, +r[i]);

		if(r[i] >= 1)
			S.add(i+1, i+K-1, +1);

		if(r[i] != 0)
			S.add(i, i, -INF);
	}





	for(int t = 0; t < N; t++)
	{
		pair<long long, int> p = S.rangemax(0, N-1);
		int I = p.second;
		h.push_back(I);
		// cerr << "I = " << I << '\n';

		R.add(I, I, +INF);
		S.add(I, I, -INF);
		S.add(I+1, I+K-1, +1);


		vector<int> newzeros;
		// R.add(I+1, I+K-1, -1);
		R.add(I-K+1, I-1, -1);
		while(1)
		{
			// for(int i = 0; i < N; i++) cerr << R.rangemin(i, i).second << ' ';
			// cerr << '\n';


			pair<long long, int> q = R.rangemin(I-K+1, I-1);
			if(q.first > 0) break;
			// cerr << "q = " << q.second << '\n';
			newzeros.push_back(q.second);
			R.add(q.second, q.second, +1);
		}
		for(int z: newzeros)
		{
			R.add(z, z, -1);
			S.add(z, z, +INF);
		}

		for(int z: newzeros)
			S.add(z+1, z+K-1, -1);
	}

	reverse(h.begin(), h.end());

	pos = vector<int>(N);
	for(int i = 0; i < N; i++)
		pos[ h[i] ] = i;

}

int compare_plants(int x, int y)
{
	if(pos[x] > pos[y])
		return 1;
	else
		return -1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 9 ms 588 KB Output is correct
7 Correct 97 ms 4764 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 9 ms 656 KB Output is correct
10 Correct 100 ms 4852 KB Output is correct
11 Correct 102 ms 4712 KB Output is correct
12 Correct 91 ms 4812 KB Output is correct
13 Correct 106 ms 4716 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 9 ms 588 KB Output is correct
7 Correct 97 ms 4764 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 9 ms 656 KB Output is correct
10 Correct 100 ms 4852 KB Output is correct
11 Correct 102 ms 4712 KB Output is correct
12 Correct 91 ms 4812 KB Output is correct
13 Correct 106 ms 4716 KB Output is correct
14 Correct 254 ms 9672 KB Output is correct
15 Correct 2751 ms 68528 KB Output is correct
16 Correct 257 ms 9664 KB Output is correct
17 Correct 2718 ms 68520 KB Output is correct
18 Correct 1555 ms 68564 KB Output is correct
19 Correct 2056 ms 68468 KB Output is correct
20 Correct 2515 ms 68584 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 66 ms 3676 KB Output is correct
4 Correct 1451 ms 68504 KB Output is correct
5 Correct 1894 ms 68404 KB Output is correct
6 Correct 2466 ms 68552 KB Output is correct
7 Correct 2729 ms 68660 KB Output is correct
8 Correct 2681 ms 68408 KB Output is correct
9 Correct 1624 ms 68428 KB Output is correct
10 Correct 1792 ms 68432 KB Output is correct
11 Correct 772 ms 68532 KB Output is correct
12 Correct 1783 ms 68612 KB Output is correct
13 Correct 1363 ms 68544 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -