oj.uz

Submission #303000

# Submission time Handle Problem Language Result Execution time Memory
303000 2020-09-19T16:00:05 Z 8e7 Comparing Plants (IOI20_plants) C++14
5 / 100
 117 ms 9452 KB 
#include "plants.h"
#include <iostream>
#include <algorithm>
#include <queue>
#define ll long long
#define maxn 200005
using namespace std;
vector<int> v, one, zero, ind1, ind0, arr;
int k;
int n;
int seg[4 * maxn], tag[4 * maxn];
vector<int> ze;
void ini(int cur, int l, int r) {
	if (r <= l) return;
	if (r - l == 1) {
		seg[cur] = v[l];
		return;
	}
	int mid = (l + r) / 2;
	ini(cur * 2, l, mid);
	ini(cur * 2 + 1, mid, r);
	seg[cur] = min(seg[cur * 2], seg[cur * 2 + 1]);
}
void modify(int cur, int l, int r, int ql, int qr) {
	if (r <= l || ql >= r || qr <= l) return;
	if (ql <= l && qr >= r) {
		tag[cur]++;
		return;
	}
	int mid = (l + r) / 2;
	modify(cur * 2, l, mid, ql, qr);
	modify(cur * 2 + 1, mid, r, ql, qr);
	seg[cur] = min(seg[cur * 2] - tag[cur * 2], seg[cur * 2 + 1] - tag[cur * 2 + 1]);
}
void sz(int cur, int l, int r, int x) {
	if (r <= l) return;
	//cout << l << " " << r << " " << seg[cur] - tag[cur] - x << endl;
	if (r - l == 1) {
		if (seg[cur] - tag[cur] - x == 0) {
			ze.push_back(l);
			tag[cur] = -1000000;
		}
		return;
	}
	int mid = (l + r) / 2;
	if (seg[cur * 2] - tag[cur * 2] - x - tag[cur] == 0) {
		sz(cur * 2, l, mid, x + tag[cur]);
	}
	if (seg[cur * 2 + 1] - tag[cur * 2 + 1] - x - tag[cur] == 0) {
		sz(cur * 2 + 1, mid, r, x + tag[cur]);
	}
	seg[cur] = min(seg[cur * 2] - tag[cur * 2], seg[cur * 2 + 1] - tag[cur * 2 + 1]);
}
bool cmp(int a, int b) {
	if (a < b) {
		return a + k < b;
	} else {
		return (a + k) < b + n;
	}
}
void init(int K, vector<int> r) {
	v = r;
	n = r.size();
	arr.resize(n);
	k = K;
	if (K == 2) {
		int cnt = 0, cur = 0;
		one.push_back(cnt);
		for (int i = 0;i < n;i++) {
			if (r[i] == 0) {
				ind1.push_back(cur);
				cur = i + 1;
				cnt++;
			}
			one.push_back(cnt);
		}
		if (r[n - 1] == 1) {
			for (int i = n - 1;i >= 0;i--) {
				if (one[i] == cnt) ind1[0] = i;
				one[i] %= cnt;
			}
		}
		cnt = 0, cur = 0;
		zero.push_back(cnt);
		for (int i = 0;i < n;i++) {
			if (r[i] == 1) {
				ind0.push_back(cur);
				cur = i + 1;
				cnt++;
			}
			zero.push_back(cnt);
		}
		if (r[n - 1] == 0) {
			for (int i = n - 1;i >= 0;i--) {
				if (zero[i] == cnt) ind0[0] = i;
				zero[i] %= cnt;
			}
		}
	} else {
		ini(1, 0, n);
		priority_queue<int, vector<int>, bool(*) (int, int) > pq(cmp);
		for (int i = n;i >= 1;i--) {
			sz(1, 0, n, 0);
			//cout << endl;
			for (int j:ze) {
				//cout << j << ' ';
				pq.push(j);
			}
			//cout << endl;
			ze.clear();
			int ind = pq.top();
			pq.pop();
			arr[ind] = i;
			if (ind - k + 1 < 0) {
				modify(1, 0, n, 0, ind + 1);
				modify(1, 0, n, n - k + ind + 1, n);
			} else {
				modify(1, 0, n, ind - k + 1, ind + 1);
			}
		}
		//for (int i = 0;i < n;i++) cout << arr[i] << " ";
		//cout << endl;
	}
	return;
}

int compare_plants(int x, int y) {
	if (k == 2) {
		if (one[x] != one[y] && zero[x] != zero[y]) {
			return 0;
		} else {
			if (one[x] == one[y]) {
				//cout <<(x - ind1[one[x]] + n) % n << " " << (y - ind1[one[y]] + n) % n << endl;
				if ((x - ind1[one[x]] + n) % n < (y - ind1[one[y]] + n) % n) return -1;
				else return 1;
			} else {
				if ((x - ind0[zero[x]] + n) % n < (y - ind0[zero[y]] + n) % n) return 1;
				else return -1;
			}
		}
	} else {
		return arr[x] > arr[y] ? 1 : -1;
	}
}
/*
5 1 3
1 1 0 0 1
0 1
0 3
2 4


7 4 5
3 1 2 2 0 1 2
0 3
2 4
3 6
1 5
2 5
 */

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 64 ms 3192 KB Output is correct
7 Correct 90 ms 3960 KB Output is correct
8 Correct 117 ms 9192 KB Output is correct
9 Correct 117 ms 9452 KB Output is correct
10 Correct 114 ms 8936 KB Output is correct
11 Correct 112 ms 8808 KB Output is correct
12 Correct 115 ms 8692 KB Output is correct
13 Correct 111 ms 8964 KB Output is correct
14 Correct 112 ms 8940 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 64 ms 3192 KB Output is correct
7 Correct 90 ms 3960 KB Output is correct
8 Correct 117 ms 9192 KB Output is correct
9 Correct 117 ms 9452 KB Output is correct
10 Correct 114 ms 8936 KB Output is correct
11 Correct 112 ms 8808 KB Output is correct
12 Correct 115 ms 8692 KB Output is correct
13 Correct 111 ms 8964 KB Output is correct
14 Correct 112 ms 8940 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 0 ms 256 KB Output is correct
18 Incorrect 0 ms 384 KB Output isn't correct
19 Halted 0 ms 0 KB -