oj.uz

Submission #1049915

# Submission time Handle Problem Language Result Execution time Memory
1049915 2024-08-09T06:07:19 Z fuad27 Comparing Plants (IOI20_plants) C++17
44 / 100
 283 ms 18772 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

struct lazy_segtree {
	vector<pair<int,int>> T;
	vector<int> lz;
	int n;
	void build(vector<int> &a, int tl, int tr, int v) {
		if(tl == tr) {
			T[v] = {a[tl], tl};
			return;
		}
		int tm = (tl+tr)/2;
		build(a, tl, tm, 2*v);
		build(a, tm+1, tr, 2*v+1);
		T[v] = min(T[2*v], T[2*v+1]);

	}
	lazy_segtree(vector<int> &a) {
		n=a.size();	
		T.resize(4*n);
		lz.resize(4*n);
		build(a, 0, n-1, 1);
	}
	void push(int v){
		lz[2*v] += lz[v];
		lz[2*v+1] += lz[v];
		T[2*v].first += lz[v];
		T[2*v+1].first += lz[v];
		lz[v] = 0;
	}
	void update(int l, int r, int add, int tl, int tr, int v) {
		if(r < tl or tr < l)return;
		if(l <= tl and tr<=r) {
			lz[v]+=add;
			T[v].first+=add;
			return;
		}
		push(v);
		int tm=(tl+tr)/2;
		update(l, r, add, tl, tm, 2*v);
		update(l, r, add, tm+1, tr, 2*v+1);
		T[v] = min(T[2*v], T[2*v+1]);
	}
	pair<int,int> query(int l, int r, int tl, int tr, int v) {
		if(r < tl or tr < l)return {1e9, 1e9};
		if(l <= tl and tr<=r)return T[v];
		push(v);
		int tm=(tl+tr)/2;
		return min(query(l, r, tl, tm, 2*v), query(l, r, tm+1, tr, 2*v+1));
	}
	void update(int l, int r, int add) {
		update(l, r, add, 0, n-1, 1);
	}
	pair<int,int> query(int l, int r) {
		return query(l, r, 0, n-1, 1);
	}
};

vector<int> H;

void init(int k, std::vector<int> r) {
	int n = r.size();
	lazy_segtree ls(r);
	int cnt = n;
	H.resize(n, -1);
	auto dfs = [&](int at, auto &&dfs) -> void {
		if(at >= k-1) {
			pair<int,int> val = ls.query(at-k+1, at-1);
			while(val.first == 0) {
				dfs(val.second, dfs);
				val = ls.query(at-k+1, at-1);
			}
			H[at] = cnt--;
			ls.update(at-k+1, at-1, -1);
			ls.update(at, at, 1e9);
		}
		else {
			pair<int,int> val = min(ls.query(0, at-1), ls.query(n-k+at+1, n-1));
			while(val.first == 0) {
				dfs(val.second, dfs);
				val = min(ls.query(0, at-1), ls.query(n-k+at+1, n-1));
			}
			H[at] = cnt--;
			ls.update(0, at-1, -1), ls.update(n-k+at+1, n-1, -1);
			ls.update(at, at, 1e9);
		}
	};
	while(ls.query(0, n-1).first == 0) {
		dfs(ls.query(0, n-1).second, dfs);
	}
	return;
}

int compare_plants(int x, int y) {
	if(H[x] < H[y])return -1;
	return 1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 30 ms 3172 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 30 ms 3188 KB Output is correct
11 Correct 28 ms 3284 KB Output is correct
12 Correct 28 ms 3508 KB Output is correct
13 Correct 30 ms 3256 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 30 ms 3172 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 30 ms 3188 KB Output is correct
11 Correct 28 ms 3284 KB Output is correct
12 Correct 28 ms 3508 KB Output is correct
13 Correct 30 ms 3256 KB Output is correct
14 Correct 47 ms 3924 KB Output is correct
15 Correct 247 ms 14420 KB Output is correct
16 Correct 46 ms 5976 KB Output is correct
17 Correct 283 ms 18256 KB Output is correct
18 Correct 183 ms 17828 KB Output is correct
19 Correct 179 ms 18276 KB Output is correct
20 Correct 229 ms 18256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 33 ms 3312 KB Output is correct
4 Correct 172 ms 18772 KB Output is correct
5 Correct 180 ms 17992 KB Output is correct
6 Correct 227 ms 17744 KB Output is correct
7 Correct 272 ms 18000 KB Output is correct
8 Correct 262 ms 18012 KB Output is correct
9 Correct 157 ms 17752 KB Output is correct
10 Correct 178 ms 17568 KB Output is correct
11 Correct 130 ms 17236 KB Output is correct
12 Correct 155 ms 17644 KB Output is correct
13 Correct 184 ms 17496 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #7
0 / 25.0

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