oj.uz

Submission #414460

# Submission time Handle Problem Language Result Execution time Memory
414460 2021-05-30T12:52:27 Z abdzag Comparing Plants (IOI20_plants) C++17
14 / 100
 122 ms 54828 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(1e5+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 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Incorrect 1 ms 972 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 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 1088 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 1084 KB Output is correct
6 Correct 5 ms 1228 KB Output is correct
7 Correct 87 ms 6256 KB Output is correct
8 Correct 3 ms 1100 KB Output is correct
9 Correct 5 ms 1228 KB Output is correct
10 Correct 70 ms 6344 KB Output is correct
11 Correct 66 ms 6340 KB Output is correct
12 Correct 68 ms 6380 KB Output is correct
13 Correct 71 ms 6340 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 1088 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 1084 KB Output is correct
6 Correct 5 ms 1228 KB Output is correct
7 Correct 87 ms 6256 KB Output is correct
8 Correct 3 ms 1100 KB Output is correct
9 Correct 5 ms 1228 KB Output is correct
10 Correct 70 ms 6344 KB Output is correct
11 Correct 66 ms 6340 KB Output is correct
12 Correct 68 ms 6380 KB Output is correct
13 Correct 71 ms 6340 KB Output is correct
14 Correct 110 ms 8192 KB Output is correct
15 Runtime error 122 ms 54828 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 2 ms 1084 KB Output is correct
3 Incorrect 1 ms 1100 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 972 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Incorrect 1 ms 1088 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 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 1 ms 972 KB Output is correct
4 Incorrect 1 ms 972 KB Output isn't correct
5 Halted 0 ms 0 KB -