oj.uz

Submission #414472

# Submission time Handle Problem Language Result Execution time Memory
414472 2021-05-30T13:07:50 Z abdzag Comparing Plants (IOI20_plants) C++17
44 / 100
 721 ms 32284 KB 
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define trav(a,v) for(auto& a: v)
#define sz(v) v.size()
#define all(v) v.begin(),v.end()
#define vi vector<int>

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int inf = -1e9;

using namespace std;

vector<ll> sorted(3e5);
static const int infint = 1e9;
struct Node {
	Node* l = 0, * r = 0;
	int lo, hi, madd = 0, mset = inf;

	pair<int, int> val = make_pair(-inf, -inf);
	Node(int lo, int hi) :lo(lo), hi(hi) {} // Large interval of -inf
	Node(vector<pair<int, int>>& v, int lo, int hi) : lo(lo), hi(hi) {
		if (lo + 1 < hi) {
			int mid = lo + (hi - lo) / 2;
			l = new Node(v, lo, mid); r = new Node(v, mid, hi);
			val = min(l->val, r->val);
		}
		else val = v[lo];
	}
	pair<int, int> query(int L, int R) {
		if (R <= lo || hi <= L) return make_pair(-inf, -inf);
		if (L <= lo && hi <= R) return val;
		push();
		return min(l->query(L, R), r->query(L, R));
	}
	void set(int L, int R, int x) {
		if (R <= lo || hi <= L) return;
		if (L <= lo && hi <= R) mset = val.first = x, madd = 0;
		else {
			push(), l->set(L, R, x), r->set(L, R, x);
			val = min(l->val, r->val);
		}
	}
	void add(int L, int R, int x) {
		if (R <= lo || hi <= L) return;
		if (L <= lo && hi <= R) {
			if (mset != inf) mset += x;
			else madd += x;
			val.first += x;
		}
		else {
			push(), l->add(L, R, x), r->add(L, R, x);
			val = min(l->val, r->val);
		}
	}
	void push() {
		if (!l) {
			int mid = lo + (hi - lo) / 2;
			l = new Node(lo, mid); r = new Node(mid, hi);
		}
		if (mset != inf)
			l->set(lo, hi, mset), r->set(lo, hi, mset), mset = inf;
		else if (madd)
			l->add(lo, hi, madd), r->add(lo, hi, madd), madd = 0;
	}
};
ll counter = 0;
void extract(Node*& tree, ll cur, ll k, ll n) {
	if (cur - k + 1 < 0) {
		while (!tree->query(0, cur).first) {
			extract(tree, tree->query(0, cur).second, k, n);
		}
		while (!tree->query(n - (k - 1 - cur), n).first) {
			extract(tree, tree->query(n - (k - 1 - cur), n).second, k, n);
		}
		tree->add(0, cur, -1);
		tree->add(n - (k - 1 - cur), n, -1);
	}
	else {
		while (!tree->query(cur - k + 1, cur).first) {
			extract(tree, tree->query(cur - k + 1, cur).second, k, n);
		}
		tree->add(cur - k + 1, cur, -1);
	}
	tree->set(cur, cur + 1, infint);
	sorted[cur] = counter++;
	return;
}
void init(int k, std::vector<int> r) {
	ll n = r.size();
	ll indx = 0;
	vector<pair<int, int>> v;
	rep(i, 0, n)v.emplace_back(r[i], i);
	Node* tree = new Node(v, 0, n);
	rep(i, 0, n) {
		pair<int, int> val = tree->query(0, n);
		if (val.first == 0)extract(tree, val.second, k, n);
		else break;
	}
}

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

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:93:5: warning: unused variable 'indx' [-Wunused-variable]
   93 |  ll indx = 0;
      |     ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Incorrect 2 ms 2636 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 3 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 6 ms 2764 KB Output is correct
7 Correct 71 ms 5912 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 5 ms 2820 KB Output is correct
10 Correct 68 ms 5936 KB Output is correct
11 Correct 66 ms 5904 KB Output is correct
12 Correct 83 ms 6036 KB Output is correct
13 Correct 73 ms 6036 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 6 ms 2764 KB Output is correct
7 Correct 71 ms 5912 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 5 ms 2820 KB Output is correct
10 Correct 68 ms 5936 KB Output is correct
11 Correct 66 ms 5904 KB Output is correct
12 Correct 83 ms 6036 KB Output is correct
13 Correct 73 ms 6036 KB Output is correct
14 Correct 102 ms 7404 KB Output is correct
15 Correct 683 ms 26852 KB Output is correct
16 Correct 106 ms 7400 KB Output is correct
17 Correct 699 ms 26852 KB Output is correct
18 Correct 344 ms 26804 KB Output is correct
19 Correct 355 ms 26804 KB Output is correct
20 Correct 546 ms 26872 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 74 ms 7412 KB Output is correct
4 Correct 336 ms 32284 KB Output is correct
5 Correct 440 ms 30168 KB Output is correct
6 Correct 626 ms 30172 KB Output is correct
7 Correct 721 ms 30292 KB Output is correct
8 Correct 692 ms 30516 KB Output is correct
9 Correct 327 ms 30032 KB Output is correct
10 Correct 328 ms 29912 KB Output is correct
11 Correct 258 ms 29792 KB Output is correct
12 Correct 311 ms 29948 KB Output is correct
13 Correct 335 ms 30036 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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