oj.uz

Submission #826927

# Submission time Handle Problem Language Result Execution time Memory
826927 2023-08-16T06:53:11 Z tomruk Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 3788 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define N 200005
using namespace std;
struct SegTree{
	vector<pair<int,int>> t;
	vector<int> lazy;
	int n;
	SegTree(int sz,vector<int> a){
		n = sz;
		t.assign(4*n,{0,0});
		lazy.assign(4*n,0);
		build(1,0,n-1,a);
	}
	void build(int v,int tl,int tr,vector<int> &a){
		if(tl == tr){
			t[v] = {a[tl],tl};
			return;
		}
		int tm = (tl + tr)/2;
		build(v*2,tl,tm,a);
		build(v*2 + 1,tm+1,tr,a);
		t[v] = t[v*2];
		if(t[v*2 + 1].first < t[v].first)
			t[v] = t[v*2+1];
	}
	void push(int v){
		t[v*2].first += lazy[v];
		lazy[v*2] += lazy[v];
		t[v*2 + 1].first += lazy[v];
		lazy[v*2 + 1] += lazy[v];
		lazy[v] = 0;
	}
	void upd(int v,int tl,int tr,int l,int r,int val){
		if(tr < l || r < tl)
			return;
		if(l <= tl && tr <= r){
			t[v].first += val;
			lazy[v] += val;
			return;
		}
		push(v);
		int tm = (tl + tr)/2;
		upd(v*2,tl,tm,l,r,val);
		upd(v * 2 + 1,tm+1,tr,l,r,val);
		t[v] = t[v*2];
		if(t[v*2 + 1].first < t[v].first)
			t[v] = t[v*2+1];
	}
	pair<int,int> get(int v,int tl,int tr,int l,int r){
		if(tr < l || r < tl)
			return {1e9,0};
		if(l <= tl && tr <= r){
			return t[v];
		}
		push(v);
		int tm = (tl + tr)/2;
		auto a = get(v*2,tl,tm,l,r);
		auto b = get(v*2+1,tm+1,tr,l,r);
		if(b.first < a.first)
			return b;
		return a;
	}
	void upd(int l,int r,int val){
		upd(1,0,n-1,l,r,val);
	}
	pair<int,int> get(int l,int r){
		return get(1,0,n-1,l,r);
	}
};
int k;
int a[N];
void init(int k, vector<int> r) {
	int n  = r.size();
	SegTree t(n,r);
	// for(int i = n-1;i>=0;i--){
	// 	auto p1 = t.get(0,n-1);
	// 	auto p2 = t.get(p1.second + k,n-1);
	// 	if(p2.first == 0)
	// 		p1 = p2;
	// 	assert(p1.first == 0);
	// 	a[p1.second] = i;
	// 	if(p1.second)
	// 		t.upd(max(0,p1.second-k + 1),p1.second - 1,-1);
	// 	if(p1.second - k + 1 < 0){
	// 		t.upd(p1.second-k + 1 + n,n-1,-1);
	// 	}
	// 	t.upd(p1.second,p1.second,1e9);
	// 	// for(int j = 0;j<=n-1;j++){
	// 	// 	cout << t.get(j,j).first << ' ';
	// 	// }
	// 	// cout << endl;
	// 	// cout << i << ' ' << p1.second << endl;
	// }
	for(int i = n-1;i>=0;){
		vector<int> p;
		for(int j = 0;j<n;j++){
			if(t.get(j,j).first == 0)
				p.push_back(j);
		}
		vector<int> tmp;
		int maxi = -1e9;
		for(auto u:p){
			if(tmp.empty() || maxi + k - 1 < u)
				tmp.push_back(u);
			maxi = u;
		}
		int x = tmp.back() + k-1 - n;
		p.clear();
		for(auto u:tmp){
			if(u <= x)
				continue;
			p.push_back(u);
		}
		assert(p.size());
		for(auto u:p){
			if(u)
				t.upd(max(0,u-k + 1),u - 1,-1);
			if(u - k + 1 < 0){
				t.upd(u-k + 1 + n,n-1,-1);
			}
			t.upd(u,u,1e9);
			a[u] = i;
		}
		i -= p.size();
	}
}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 55 ms 404 KB Output is correct
7 Correct 2053 ms 3248 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 54 ms 416 KB Output is correct
10 Correct 2087 ms 3192 KB Output is correct
11 Correct 2082 ms 3204 KB Output is correct
12 Correct 2041 ms 3324 KB Output is correct
13 Correct 2134 ms 3200 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 55 ms 404 KB Output is correct
7 Correct 2053 ms 3248 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 54 ms 416 KB Output is correct
10 Correct 2087 ms 3192 KB Output is correct
11 Correct 2082 ms 3204 KB Output is correct
12 Correct 2041 ms 3324 KB Output is correct
13 Correct 2134 ms 3200 KB Output is correct
14 Execution timed out 4050 ms 3788 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 340 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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