oj.uz

Submission #302999

# Submission time Handle Problem Language Result Execution time Memory
302999 2020-09-19T15:56:30 Z 8e7 Comparing Plants (IOI20_plants) C++14
5 / 100
 115 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 1 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 78 ms 3192 KB Output is correct
7 Correct 82 ms 3832 KB Output is correct
8 Correct 115 ms 9192 KB Output is correct
9 Correct 113 ms 9452 KB Output is correct
10 Correct 114 ms 8844 KB Output is correct
11 Correct 112 ms 8936 KB Output is correct
12 Correct 112 ms 8820 KB Output is correct
13 Correct 111 ms 8932 KB Output is correct
14 Correct 115 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 0 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Incorrect 1 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 0 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Incorrect 1 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 0 ms 384 KB Output is correct
3 Incorrect 74 ms 3192 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 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 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 0 ms 256 KB Output is correct
4 Incorrect 1 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 78 ms 3192 KB Output is correct
7 Correct 82 ms 3832 KB Output is correct
8 Correct 115 ms 9192 KB Output is correct
9 Correct 113 ms 9452 KB Output is correct
10 Correct 114 ms 8844 KB Output is correct
11 Correct 112 ms 8936 KB Output is correct
12 Correct 112 ms 8820 KB Output is correct
13 Correct 111 ms 8932 KB Output is correct
14 Correct 115 ms 8940 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 0 ms 256 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Incorrect 1 ms 384 KB Output isn't correct
19 Halted 0 ms 0 KB -