oj.uz

Submission #414461

# Submission time Handle Problem Language Result Execution time Memory
414461 2021-05-30T12:53:16 Z abdzag Comparing Plants (IOI20_plants) C++17
27 / 100
 876 ms 30644 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+1);
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;
	}
};
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);
	rrep(j, n - 1, -1) {
		if (r[j] == 0) {
			indx = j;
			break;
		}
	}
	ll cur = 0;
	rep(j, 0, n) {
		cur++;
		if (r[(indx + j) % n] == 0) {
			if (cur > k) {
				indx = (j + indx) % n;
				break;
			}
			else cur = 1;
		}
	}
	rep(i, 0, n) {
		tree->set(indx, indx + 1, 1e9);
		sorted[indx] = i;
		ll left = indx;
		left -= (k - 1);
		left += n;
		left %= n;
		if (left + k - 1 > n) {
			tree->add(left, n, -1);
			tree->add(0, left + k - n - 1, -1);
			pair<int, int> val = tree->query(left, n);
			if (val.first == 0) {
				left = val.second;
				left -= (k - 1);
				left += n;
				left %= n;
				pair<int, int> val0 = val;
				if (left + k - 1 > n) {
					val = tree->query(left, n);
					val = min(val, tree->query(0, left + k - n - 1));
				}
				else {
					val = tree->query(left, left + k - 1);
				}
				if (val.first != 0) {
					indx = val0.second;
					continue;
				}
			}
			val = tree->query(0, left + k - n);
			if (val.first == 0) {
				left = val.second;
				left -= (k - 1);
				left += n;
				left %= n;
				pair<int, int> val0 = val;
				if (left + k - 1 > n) {
					val = tree->query(left, n);
					val = min(val, tree->query(0, left + k - n - 1));
				}
				else {
					val = tree->query(left, left + k - 1);
				}
				if (val.first != 0) {
					indx = val0.second;
					continue;
				}
			}
		}
		else {
			tree->add(left, left + k - 1, -1);
			pair<int, int> val = tree->query(left, left + k);
			if (val.first == 0) {
				left = val.second;
				left -= (k - 1);
				left += n;
				left %= n;
				pair<int, int> val0 = val;
				if (left + k - 1 > n) {
					val = tree->query(left, n);
					val = min(val, tree->query(0, left + k - n - 1));
				}
				else {
					val = tree->query(left, left + k - 1);
				}
				if (val.first != 0) {
					indx = val0.second;
					continue;
				}
			}
		}
		if (indx + k > n) {
			pair<int, int> val = tree->query(indx, n);
			if (val.first == 0) {
				indx = val.second;
			}
			else indx = tree->query(0, indx + k - n).second;
		}
		else indx = tree->query(indx, indx + k).second;
	}
}

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

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 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 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 7 ms 2764 KB Output is correct
7 Correct 80 ms 5912 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 5 ms 2764 KB Output is correct
10 Correct 69 ms 5956 KB Output is correct
11 Correct 65 ms 6036 KB Output is correct
12 Correct 65 ms 6040 KB Output is correct
13 Correct 72 ms 5924 KB Output is correct

Subtask #3
13.0 / 13.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 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 7 ms 2764 KB Output is correct
7 Correct 80 ms 5912 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 5 ms 2764 KB Output is correct
10 Correct 69 ms 5956 KB Output is correct
11 Correct 65 ms 6036 KB Output is correct
12 Correct 65 ms 6040 KB Output is correct
13 Correct 72 ms 5924 KB Output is correct
14 Correct 116 ms 7520 KB Output is correct
15 Correct 876 ms 26856 KB Output is correct
16 Correct 116 ms 9628 KB Output is correct
17 Correct 864 ms 30548 KB Output is correct
18 Correct 465 ms 30132 KB Output is correct
19 Correct 444 ms 30644 KB Output is correct
20 Correct 726 ms 30584 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.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 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 2636 KB Output is correct
2 Correct 2 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 -