oj.uz

Submission #1020573

# Submission time Handle Problem Language Result Execution time Memory
1020573 2024-07-12T07:07:34 Z alex_2008 Comparing Plants (IOI20_plants) C++14
27 / 100
 239 ms 19024 KB 
#include "plants.h"
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
int r[N], perm[N];
pair<int, int> tree[4 * N];
int lazy[4 * N];
int val[N];
int n, k;
int prev(int x, int n) {
	if (x > 1) return x - 1;
	return n;
}
void pushh(int v, int tl, int tr) {
	if (lazy[v]) {
		if (tl != tr) {
			lazy[2 * v] += lazy[v];
			lazy[2 * v + 1] += lazy[v];
			tree[2 * v].first -= lazy[v];
			tree[2 * v + 1].first -= lazy[v];
		}
		lazy[v] = 0;
	}
}
void build_tree(int v, int tl, int tr) {
	if (tl == tr) {
		tree[v] = { r[tl], tl };
		return;
	}
	int tm = (tl + tr) / 2;
	build_tree(2 * v, tl, tm);
	build_tree(2 * v + 1, tm + 1, tr);
	if (tree[2 * v].first <= tree[2 * v + 1].first) tree[v] = tree[2 * v];
	else tree[v] = tree[2 * v + 1];
}
void update_range(int v, int tl, int tr, int l, int r) {
	if (tl > r || tr < l) return;
	if (tl >= l && tr <= r) {
		tree[v].first--;
		lazy[v]++;
		return;
	}
	pushh(v, tl, tr);
	int tm = (tl + tr) / 2;
	update_range(2 * v, tl, tm, l, r);
	update_range(2 * v + 1, tm + 1, tr, l, r);
	if (tree[2 * v].first <= tree[2 * v + 1].first) tree[v] = tree[2 * v];
	else tree[v] = tree[2 * v + 1];
}
void update_pos(int v, int tl, int tr, int pos) {
	if (tl > pos || tr < pos) return;
	if (tl == tr) {
		lazy[v] = 0;
		tree[v] = { N, tl };
		return;
	}
	pushh(v, tl, tr);
	int tm = (tl + tr) / 2;
	update_pos(2 * v, tl, tm, pos);
	update_pos(2 * v + 1, tm + 1, tr, pos);
	if (tree[2 * v].first <= tree[2 * v + 1].first) tree[v] = tree[2 * v];
	else tree[v] = tree[2 * v + 1];
}
pair <int, int> Mn_In_Range(int v, int tl, int tr, int l, int r) {
	if (tl > r || tr < l) return { N + 1, -1 };
	if (tl >= l && tr <= r) return tree[v];
	pushh(v, tl, tr);
	int tm = (tl + tr) / 2;
	pair <int, int> v1 = Mn_In_Range(2 * v, tl, tm, l, r);
	pair <int, int> v2 = Mn_In_Range(2 * v + 1, tm + 1, tr, l, r);
	if (v1.first <= v2.first) return v1;
	return v2;
}
void init(int K, vector<int> R) {
	k = K;
	n = (int)R.size();
	for (int i = 1; i <= n; i++) {
		r[i] = R[i - 1];
	}
	build_tree(1, 1, n);
	for (int i = n; i >= 1; i--) {
		/*int last = -1;
		for (int j = 1; j <= n; j++) {
			if (r[j] != 0) continue;
			if (last == -1 || (last + (k - 1) < j)) last = j;
		}
		r[last] = N;
		perm[last] = i;
		int q = k - 1, ind = prev(last, n);
		while (q--) {
			r[ind]--;
			ind = prev(ind, n);
		}*/
		int ind = Mn_In_Range(1, 1, n, 1, n).second;
		//cout << "? " << ind << "\n";
		if (ind + k <= n) {
			//cout << "# ";
			pair <int, int> esim = Mn_In_Range(1, 1, n, ind + k, n);
			//cout << esim.first << " " << esim.second << "\n";
			if (esim.first == 0) {
				ind = esim.second;
			}
		}
		//cout << "!" << ind << "\n";
		perm[ind] = i;
		update_pos(1, 1, n, ind);
		if (ind >= k) {
			//cout << "[ " << ind - k + 1 << " " << ind - 1 << " ]\n";
			update_range(1, 1, n, ind - k + 1, ind - 1);
		}
		else {
			update_range(1, 1, n, 1, ind - 1);
			//cout << "[ " << 1 << " " << ind - 1 << " ] ";
			int mnac = k - ind;
			update_range(1, 1, n, n - mnac + 1, n);
			//cout << "[ " << n - mnac + 1 << " " << n << " ]\n";
		}
	}
}
int compare_plants(int x, int y) {
	x++; y++;
	if (perm[x] > perm[y]) return 1;
	return -1;
}
/*
int main() {
	init(3, { 2, 1, 0, 2, 1 });
	for (int i = 1; i <= 5; i++) {
		cout << perm[i] << " ";
	}
}
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Incorrect 1 ms 4444 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 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4544 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4440 KB Output is correct
7 Correct 37 ms 9300 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 35 ms 9300 KB Output is correct
11 Correct 36 ms 9296 KB Output is correct
12 Correct 35 ms 9304 KB Output is correct
13 Correct 35 ms 9296 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4544 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4440 KB Output is correct
7 Correct 37 ms 9300 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 35 ms 9300 KB Output is correct
11 Correct 36 ms 9296 KB Output is correct
12 Correct 35 ms 9304 KB Output is correct
13 Correct 35 ms 9296 KB Output is correct
14 Correct 54 ms 11952 KB Output is correct
15 Correct 235 ms 18932 KB Output is correct
16 Correct 56 ms 12112 KB Output is correct
17 Correct 239 ms 19024 KB Output is correct
18 Correct 145 ms 18420 KB Output is correct
19 Correct 140 ms 19024 KB Output is correct
20 Correct 207 ms 19024 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 1 ms 4440 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 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Incorrect 1 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -