oj.uz

Submission #823510

# Submission time Handle Problem Language Result Execution time Memory
823510 2023-08-12T15:59:10 Z fatemetmhr Comparing Plants (IOI20_plants) C++17
44 / 100
 977 ms 81708 KB 
// vaghan ide i nadaram chi benevisam dige :/


#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define fi     first
#define se     second
#define mp     make_pair
#define pb     push_back

typedef long long ll;

const int maxn5 = 2e5 + 10;
const int maxnt = 1e6 + 10;
const int lg    = 20;
const int maxn3 = 310;
const int mod   = 1e9 + 10;

int n, ind[maxn5], ed[2][lg][maxn5];
vector <int> av;

namespace seg3{

	pair <int, int> mn[maxnt];

	void build(int l, int r, int v){
		mn[v] = {maxn5, -1};
		if(r - l == 1)
			return;
		int mid = (l + r) >> 1;
		build(l, mid, v * 2);
		build(mid, r, v * 2 + 1);
	}

	void upd(int l, int r, int id, int val, int v){
		if(r - l == 1){
			mn[v] = {val, l};
			return;
		}
		int mid = (l + r) >> 1;
		if(id < mid)
			upd(l, mid, id, val, v * 2);
		else
			upd(mid, r, id, val, v * 2 + 1);
		mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
	}

	pair <int, int> get_min(int l, int r, int lq, int rq, int v){
		if(rq <= l || r <= lq)
			return mp(maxn5, -1);
		if(lq <= l && r <= rq)
			return mn[v];
		int mid = (l + r) >> 1;
		return min(get_min(l, mid, lq, rq, v * 2), get_min(mid, r, lq, rq, v * 2 + 1));
	}
}



struct seg{

	ll lazy[maxnt];
	pair <ll, int> mn[maxnt];

	void upd(int l, int r, int id, int val, int v){
		if(r - l == 1){
			lazy[v] = 0;
			mn[v] = {val, l};
			return;
		}
		int mid = (l + r) >> 1;
		if(id < mid)
			upd(l, mid, id, val, v * 2);
		else
			upd(mid, r, id, val, v * 2 + 1);
		mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
		mn[v].fi += lazy[v];
	}

	void add(int l, int r, int lq, int rq, int val, int v){
		if(rq <= l || r <= lq)
			return;
		if(lq <= l && r <= rq){
			lazy[v] += val;
			mn[v].fi += val;
			return;
		}
		int mid = (l + r) >> 1;
		add(l, mid, lq, rq, val, v * 2);
		add(mid, r, lq, rq, val, v * 2 + 1);
		mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
		mn[v].fi += lazy[v];
	}
} seg1, seg2;

void init(int k, vector<int> r) {
	n = r.size();
	for(int i = 0; i < n; i++){
		seg1.upd(0, n, i, r[i], 1);
		seg2.upd(0, n, i, r[i], 1);
	}
	bool con = true;
	while(con){
		con = false;
		while(seg1.mn[1].fi == 0){
			con = true;
			int v = seg1.mn[1].se;
			//cout << "ok seg1 " << v << endl;
			seg1.upd(0, n, v, mod / 2, 1);
			if(v < n - 1)
				seg2.add(0, n, v + 1, min(n, v + k), 1, 1);
			if(v + k > n)
				seg2.add(0, n, 0, v + k - n, 1, 1);
		}
		if(seg2.mn[1].fi == 0){
			con = true;
			int v = seg2.mn[1].se;
			//cout << "ok seg2 " << v << ' ' << k << ' ' << (v - (k - 1)) << endl;
			av.pb(v);
			seg2.upd(0, n, v, mod / 2, 1);
			if(v < n - 1)
				seg2.add(0, n, v + 1, min(n, v + k), -1, 1);
			if(v + k > n)
				seg2.add(0, n, 0, v + k - n, -1, 1);
			if(v){
				seg1.add(0, n, max(0, v - (k - 1)), v, -1, 1);
				seg2.add(0, n, max(0, v - (k - 1)), v, -1, 1);
			}
			if(v - (k - 1) < 0){
				seg1.add(0, n, v - (k - 1) + n, n, -1, 1);
				seg2.add(0, n, v - (k - 1) + n, n, -1, 1);
			}
		}

	}
	//cout << av.size() << endl;
	reverse(all(av));
	for(int i = 0; i < n; i++){
		ind[av[i]] = i;
		//cout << av[i] << ' ';
	}
	//cout << endl;
	memset(ed, -1, sizeof ed);
	seg3::build(0, n, 1);
	for(int i = n - 1; i >= 0; i--){
		int v = av[i];
		pair <int, int> ans1 = {maxn5, -1}, ans2 = {maxn5, -1};
		if(v < n - 1)
			ans1 = seg3::get_min(0, n, v, min(n, v + k), 1);
		if(v + k > n)
			ans2 = seg3::get_min(0, n, 0, v + k - n, 1);
		ans1 = min(ans1, ans2);
		ed[0][0][v] = ans1.se;
		ans1 = ans2 = {maxn5, -1};
		if(v)
			ans1 = seg3::get_min(0, n, max(0, v - k + 1), v, 1);
		if(v - k + 1 < 0)
			ans2 = seg3::get_min(0, n, v - k + 1 + n, n, 1);
		ans1 = min(ans1, ans2);
		ed[1][0][v] = ans1.se;
		seg3::upd(0, n, v, i, 1);
	}
	for(int i = 1; i < lg; i++) for(int j = 0; j < n; j++){
		if(ed[0][i - 1][j] != -1)
			ed[0][i][j] = ed[0][i - 1][ed[0][i - 1][j]];
		if(ed[1][i - 1][j] != -1)
			ed[1][i][j] = ed[1][i - 1][ed[1][i - 1][j]];
	}
	return;
}

int find_first(int x, int lim, int ty){
	for(int i = lg - 1; i >= 0; i--)
		if(ed[ty][i][x] != -1 && ind[ed[ty][i][x]] <= lim)
			x = ed[ty][i][x];
	return x;
}

int compare_plants(int x, int y) {
	if(ind[x] < ind[y])
		return -1;
	return 1;
	int sw = -1;
	if(ind[x] > ind[y]){
		swap(x, y);
		sw = 1;
	}
	int v = find_first(x, ind[y], 0);
	if((y - x + n) % n <= (v - x + n) % n)
		return sw;
	v = find_first(x, ind[y], 1);
	if((x - y + n) % n <= (x - v + n) % n)
		return sw;
	return 0;

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 62932 KB Output is correct
2 Correct 21 ms 62916 KB Output is correct
3 Correct 20 ms 62932 KB Output is correct
4 Incorrect 20 ms 62932 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 19 ms 62832 KB Output is correct
2 Correct 20 ms 62904 KB Output is correct
3 Correct 20 ms 62864 KB Output is correct
4 Correct 20 ms 62848 KB Output is correct
5 Correct 21 ms 62932 KB Output is correct
6 Correct 25 ms 62988 KB Output is correct
7 Correct 71 ms 66276 KB Output is correct
8 Correct 21 ms 63016 KB Output is correct
9 Correct 26 ms 63088 KB Output is correct
10 Correct 71 ms 66260 KB Output is correct
11 Correct 65 ms 66132 KB Output is correct
12 Correct 64 ms 66308 KB Output is correct
13 Correct 71 ms 66280 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 62832 KB Output is correct
2 Correct 20 ms 62904 KB Output is correct
3 Correct 20 ms 62864 KB Output is correct
4 Correct 20 ms 62848 KB Output is correct
5 Correct 21 ms 62932 KB Output is correct
6 Correct 25 ms 62988 KB Output is correct
7 Correct 71 ms 66276 KB Output is correct
8 Correct 21 ms 63016 KB Output is correct
9 Correct 26 ms 63088 KB Output is correct
10 Correct 71 ms 66260 KB Output is correct
11 Correct 65 ms 66132 KB Output is correct
12 Correct 64 ms 66308 KB Output is correct
13 Correct 71 ms 66280 KB Output is correct
14 Correct 119 ms 67652 KB Output is correct
15 Correct 977 ms 80852 KB Output is correct
16 Correct 118 ms 67628 KB Output is correct
17 Correct 874 ms 80880 KB Output is correct
18 Correct 492 ms 80992 KB Output is correct
19 Correct 490 ms 80808 KB Output is correct
20 Correct 775 ms 81004 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 62916 KB Output is correct
2 Correct 21 ms 62936 KB Output is correct
3 Correct 59 ms 65868 KB Output is correct
4 Correct 431 ms 81048 KB Output is correct
5 Correct 536 ms 81512 KB Output is correct
6 Correct 705 ms 81708 KB Output is correct
7 Correct 815 ms 81548 KB Output is correct
8 Correct 893 ms 81664 KB Output is correct
9 Correct 461 ms 81388 KB Output is correct
10 Correct 473 ms 81408 KB Output is correct
11 Correct 343 ms 79408 KB Output is correct
12 Correct 403 ms 81680 KB Output is correct
13 Correct 498 ms 81556 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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