Submission #603640

#	Time	Username	Problem	Language	Result	Execution time	Memory
603640		gagik_2007	Comparing Plants (IOI20_plants)	C++17	5 / 100	87 ms	6524 KiB

plants

#include "plants.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <string>
using namespace std;

#define ff first
#define ss second

typedef long long ll;
typedef long double ld;

const int INF = 1e9 + 7;
ll n, k;
vector<int>a;
vector<int>cons0, cons1;
bool ent1 = false;
pair<int, int> t[800007];
int lazy[1600007];
vector<int>vals;

void push(int v) {
	lazy[2 * v] += lazy[v];
	lazy[2 * v + 1] += lazy[v];
	t[v].ff += lazy[v];
	lazy[v] = 0;
}

void build(int v, int tl, int tr) {
	if (tl == tr) {
		t[v] = { a[tl],tl };
	}
	else {
		int tm = (tl + tr) / 2;
		build(2 * v, tl, tm);
		build(2 * v + 1, tm + 1, tr);
		t[v] = min(t[2 * v], t[2 * v + 1]);
	}
}

pair<int, int> get_min(int v, int tl, int tr, int l, int r) {
	push(v);
	if (l > r)return { INF,INF };
	if (tl >= l && tr <= r)return t[v];
	else {
		int tm = (tl + tr) / 2;
		return min(get_min(2 * v, tl, tm, l, min(r, tm)),
			get_min(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
	}
}

void update(int v, int tl, int tr, int ind, int val) {
	push(v);
	if (tl == tr) {
		t[v].ff = val;
		//cout << "Updating: ";
		//cout << t[v].ff << " " << t[v].ss << endl;
	}
	else {
		int tm = (tl + tr) / 2;
		if (ind <= tm) {
			update(2 * v, tl, tm, ind, val);
		}
		else update(2 * v + 1, tm + 1, tr, ind, val);
		t[v] = min(t[2 * v], t[2 * v + 1]);
	}
}

void add_r(int v, int tl, int tr, int l, int r, int val) {
	push(v);
	if (l > r)return;
	if (tl >= l && tr <= r) {
		lazy[v] += val;
		push(v);
	}
	else {
		int tm = (tl + tr) / 2;
		add_r(2 * v, tl, tm, l, min(r, tm), val);
		add_r(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, val);
		t[v] = min(t[2 * v], t[2 * v + 1]);
	}
}

int her(int x, int y) {
	if (y < x)y += n;
	return y - x;
}

void init(int K, vector<int> r) {
	n = r.size();
	k = K;
	a = r;
	if (k == 2) {
		ent1 = true;
		int cur0 = 0, cur1 = 0;
		int f1 = 0, f0 = 0;
		cons0.resize(n, 0);
		cons1.resize(n, 0);
		for (int i = 0; i < 2 * n; i++) {
			if (r[i % n] == 1) {
				if (cur0 != 0) {
					while (f0 != i % n) {
						cons0[f0] = cur0;
						f0++;
						cur0--;
						f0 %= n;
					}
					f1 = i % n;
				}
				cur1++;
			}
			else {
				if (cur1 != 0) {
					while (f1 != i % n) {
						cons1[f1] = cur1;
						f1++;
						cur1--;
						f1 %= n;
					}
					f0 = i % n;
				}
				cur0++;
			}
		}
		/*for (auto x : cons0) {
			cout << x << " ";
		}
		cout << endl;
		for (auto x : cons1) {
			cout << x << " ";
		}
		cout << endl;*/
	}
	else {
		build(1, 0, n - 1);
		vals.resize(n, 0);
		int curval = n;
		for (int i = 0; i < n; i++) {
			pair<int, int>mn1 = get_min(1, 0, n - 1, 0, n - 1);
			update(1, 0, n - 1, mn1.ss, INF);
			pair<int, int>mn2 = get_min(1, 0, n - 1, 0, n - 1);
			pair<int, int>mn;
			if (mn1.ff == mn2.ff) {
				if (her(mn1.ss, mn2.ss) < k) {
					mn = mn1;
				}
				else {
					update(1, 0, n - 1, mn1.ss, mn1.ff);
					update(1, 0, n - 1, mn2.ss, INF);
					mn = mn2;
				}
			}
			else {
				mn = mn1;
			}
			/*cout << "Min: ";
			cout << mn.ff << " " << mn.ss << endl;*/
			int vl = mn.ss - k + 1;
			if (vl < 0) {
				add_r(1, 0, n - 1, 0, mn.ss, -1);
				add_r(1, 0, n - 1, vl + n, n - 1, -1);
			}
			else {
				add_r(1, 0, n - 1, vl, mn.ss, -1);
			}
			vals[mn.ss] = curval--;
			/*for (int i = 0; i < n; i++) {
				cout << get_min(1, 0, n - 1, i, i).ff << " " << 
					get_min(1, 0, n - 1, i, i).ss << "  ";
			}
			cout << endl;*/
		}
	}
}

int compare_plants(int x, int y) {
	if (ent1) {
		if (cons0[x] >= her(x, y) || cons1[y] >= her(y, x)) {
			return 1;
		}
		if (cons1[x] >= her(x, y) || cons0[y] >= her(y, x)) {
			return -1;
		}
		return 0;
	}
	else {
		if (vals[x] > vals[y])return 1;
		else return -1;
	}
}

/*
4 2 3
1 1 0 0
0 1
0 2
0 3

4 3 6 0 1 1 2 0 1 0 2 0 3 1 2 1 3 2 3
1 1 1 -1 1 1

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

• Subtask 1: 5 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25