oj.uz

Submission #818110

# Submission time Handle Problem Language Result Execution time Memory
818110 2023-08-10T02:21:13 Z jlallas384 Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 28052 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(){
		mn.first = max(mn.first - lz, 0);
		if(l != r){
			lc->lz += lz;
			rc->lz += 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++;
			push();
		}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);
		}
	}
	void debug(){
		push();
		if(l == r){
			
		}else{
			lc->debug(), rc->debug();
		}
	}
};

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--){
		cout << endl;
		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);
		t->debug();
		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:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for(int i = 0; i < a.size(); i++){
      |                  ~~^~~~~~~~~~

Subtask #1
0 / 5.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 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 1 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 8 ms 468 KB Output is correct
7 Correct 176 ms 3564 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 8 ms 468 KB Output is correct
10 Correct 173 ms 3564 KB Output is correct
11 Correct 255 ms 3696 KB Output is correct
12 Correct 168 ms 3688 KB Output is correct
13 Correct 172 ms 3636 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 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 8 ms 468 KB Output is correct
7 Correct 176 ms 3564 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 8 ms 468 KB Output is correct
10 Correct 173 ms 3564 KB Output is correct
11 Correct 255 ms 3696 KB Output is correct
12 Correct 168 ms 3688 KB Output is correct
13 Correct 172 ms 3636 KB Output is correct
14 Correct 2096 ms 5148 KB Output is correct
15 Execution timed out 4073 ms 23756 KB Time limit exceeded
16 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 0 ms 212 KB Output is correct
3 Correct 66 ms 3304 KB Output is correct
4 Execution timed out 4075 ms 28052 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 1 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 1 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 1 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 -