oj.uz

Submission #826924

# Submission time Handle Problem Language Result Execution time Memory
826924 2023-08-16T06:48:17 Z tomruk Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 3884 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;
		for(auto u:p){
			if(tmp.empty() || tmp.back() + k - 1 < u)
				tmp.push_back(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 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 Incorrect 1 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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 62 ms 416 KB Output is correct
7 Correct 2080 ms 3212 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 55 ms 416 KB Output is correct
10 Correct 2197 ms 3196 KB Output is correct
11 Correct 2087 ms 3244 KB Output is correct
12 Correct 2106 ms 3316 KB Output is correct
13 Correct 2127 ms 3196 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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 62 ms 416 KB Output is correct
7 Correct 2080 ms 3212 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 55 ms 416 KB Output is correct
10 Correct 2197 ms 3196 KB Output is correct
11 Correct 2087 ms 3244 KB Output is correct
12 Correct 2106 ms 3316 KB Output is correct
13 Correct 2127 ms 3196 KB Output is correct
14 Execution timed out 4070 ms 3884 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 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 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -