oj.uz

Submission #818133

# Submission time Handle Problem Language Result Execution time Memory
818133 2023-08-10T02:39:20 Z jlallas384 Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 29468 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

struct tree{
	pair<int,int> mn;
	tree *lc, *rc;
	int l,r,lz = 0;
	tree(int i, int j, vector<int> &a){
		l = i, r = j;
		if(l == r){
			mn = {a[l], l};
			lc = nullptr , rc = nullptr;
		}else{
			int m = (l + r) / 2;
			lc = new tree(l, m, a), rc = new tree(m + 1, r, a);
			mn = min(lc->mn, rc->mn);
		}
	}
	void push(){
		if(l != r){
			lc->lz += lz;
			lc->mn.first = max(0, lc->mn.first - lz);
			rc->lz += lz;
			rc->mn.first = max(0, rc->mn.first - lz);
		}
		lz = 0;
	}
	void dec(int i, int j){
		push();
		if(i > j){
			dec(0, j), dec(i, r);
			return;
		}else if(r < i || j < l) return;
		else if(i <= l && r <= j){
			lz++;
			mn.first = max(mn.first - 1, 0);
		}else{
			lc->dec(i, j), rc->dec(i, j);
			mn = min(lc->mn, rc->mn);
		}
	}
	pair<int,int> qry(int i, int j){
		push();
		if(i > j) return min(qry(0, j), qry(i, r));
		if(r < i || j < l) return {1e9, 1e9};
		if(i <= l && r <= j) return mn;
		return min(lc->qry(i,j), rc->qry(i,j));
	}
	void rem(int i){
		push();
		if(l == r){
			mn.first = 1e9;
		}else{
			if(i <= lc->r) lc->rem(i);
			else rc->rem(i);
			mn = min(lc->mn, rc->mn);
		}
	}
};

vector<int> ans;
void init(int k, std::vector<int> r) {
	int n = r.size();
	ans.assign(n, -1);
	tree *t = new tree(0, n - 1, r);
	set<int> st;
	for(int i = 0; i < n; i++) if(r[i] == 0){
		st.insert(i);
	}
	for(int val = n - 1; val >= 0; val--){
		vector<int> a;
		for(int x: st){
			a.push_back(x);
		}
		int x = -1;
		for(int i = 0; i < a.size(); i++){
			int prv = (i - 1 + a.size()) % a.size();
			int d = (i == 0 ? a[i] + n - a[prv] : a[i] - a[prv]);
			if(d >= k){
				x = a[i];
			}
		}
		int l = (x - k + 1 + n) % n, r = (x - 1 + n) % n;
		t->dec(l, r);
		while(true){
			auto [v, i] = t->qry((x - k + 1 + n) % n, (x - 1 + n) % n);
			if(v != 0) break;
			else{
				t->rem(i);
				st.insert(i);
			}
		}
		assert(x != -1);
		ans[x] = val;
		st.erase(x);
		t->rem(x);
	}
}

int compare_plants(int x, int y) {
	if(ans[x] > ans[y]) return 1;
	else return -1;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for(int i = 0; i < a.size(); i++){
      |                  ~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 232 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 1 ms 212 KB Output is correct
3 Correct 1 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 3 ms 468 KB Output is correct
7 Correct 57 ms 3596 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 49 ms 3640 KB Output is correct
11 Correct 165 ms 3684 KB Output is correct
12 Correct 47 ms 3684 KB Output is correct
13 Correct 51 ms 3576 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 1 ms 212 KB Output is correct
3 Correct 1 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 3 ms 468 KB Output is correct
7 Correct 57 ms 3596 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 49 ms 3640 KB Output is correct
11 Correct 165 ms 3684 KB Output is correct
12 Correct 47 ms 3684 KB Output is correct
13 Correct 51 ms 3576 KB Output is correct
14 Correct 112 ms 5136 KB Output is correct
15 Correct 744 ms 23780 KB Output is correct
16 Correct 84 ms 5168 KB Output is correct
17 Correct 732 ms 23788 KB Output is correct
18 Execution timed out 4043 ms 29468 KB Time limit exceeded
19 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 Correct 1 ms 212 KB Output is correct
3 Correct 48 ms 3288 KB Output is correct
4 Execution timed out 4056 ms 27732 KB Time limit exceeded
5 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 256 KB Output is correct
2 Correct 1 ms 232 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 -