oj.uz

Submission #414580

# Submission time Handle Problem Language Result Execution time Memory
414580 2021-05-30T16:50:27 Z abdzag Comparing Plants (IOI20_plants) C++17
27 / 100
 3794 ms 29116 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, mset = inf, madd = 0, val = -inf;
	Node(int lo, int hi) :lo(lo), hi(hi) {} // Large interval of -inf
	Node(vi& 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];
	}
	int query(int L, int R) {
		if (R <= lo || hi <= L) return -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 = 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 += 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;
	Node* tree = new Node(r, 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);
		}
		else tree->add(left, left + k - 1, -1);
		left = -1;
		ll right = 0;
		ll l = 1, r = k;
		while (l <= r) {
			ll mid = l + (r - l) / 2;
			int val;
			if (indx + mid > n) {
				val = tree->query(indx, n);
				val = min(val, tree->query(0, indx + mid - n));
			}
			else val = tree->query(indx, indx + mid);
			if (val != 0) {
				l = mid + 1;
			}
			else {
				left = indx + mid - 1;
				r = mid - 1;
			}
		}

		int val;
		if (left != -1) {
			left %= n;
			left -= (k - 1);
			left += n;
			left %= n;
			if (left + k - 1 > n) {
				val = tree->query(left, n);
				val = min(val, tree->query(0, left + k - 1 - n));
			}
			else val = tree->query(left, left + k - 1);
			if (val != 0) {
				indx = (left + k - 1) % n;
				continue;
			}
		}
		indx -= (k - 1);
		indx += n;
		indx %= n;
		l = 0, r = k;
		while (l <= r) {
			ll mid = l + (r - l) / 2;
			int val;
			if (indx + mid > n) {
				val = tree->query(indx, n);
				val = min(val, tree->query(0, indx + mid - n));
			}
			else val = tree->query(indx, indx + mid);
			if (val != 0) {
				l = mid + 1;
			}
			else {
				right = indx + mid - 1;
				r = mid - 1;
			}
		}
		right %= n;
		indx = right;
	}
}

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 2596 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2568 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 10 ms 2764 KB Output is correct
7 Correct 94 ms 7816 KB Output is correct
8 Correct 4 ms 2664 KB Output is correct
9 Correct 9 ms 2764 KB Output is correct
10 Correct 94 ms 7804 KB Output is correct
11 Correct 78 ms 7688 KB Output is correct
12 Correct 90 ms 7932 KB Output is correct
13 Correct 92 ms 7784 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 2596 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2568 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 10 ms 2764 KB Output is correct
7 Correct 94 ms 7816 KB Output is correct
8 Correct 4 ms 2664 KB Output is correct
9 Correct 9 ms 2764 KB Output is correct
10 Correct 94 ms 7804 KB Output is correct
11 Correct 78 ms 7688 KB Output is correct
12 Correct 90 ms 7932 KB Output is correct
13 Correct 92 ms 7784 KB Output is correct
14 Correct 244 ms 9628 KB Output is correct
15 Correct 3794 ms 29052 KB Output is correct
16 Correct 248 ms 9636 KB Output is correct
17 Correct 3788 ms 29056 KB Output is correct
18 Correct 1247 ms 28632 KB Output is correct
19 Correct 2718 ms 29116 KB Output is correct
20 Correct 2762 ms 29112 KB Output is correct

Subtask #4
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 Incorrect 62 ms 6852 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Incorrect 2 ms 2652 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 2652 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 -