Submission #301627

#	Time	Username	Problem	Language	Result	Execution time	Memory
301627		maximath_1	Comparing Plants (IOI20_plants)	C++11	49 / 100	1668 ms	30704 KiB

plants

#include "plants.h"
#include <vector>
#include <iostream>
using namespace std;

#define ll long long
const ll inf = 1e18;
int n, arr[200005];
vector<int> r;

pair<ll, int> st[200005 * 4][2];

void build(int nd, int cl, int cr, int tp){
	st[nd][tp] = {0, cl};
	if(cl != cr){
		build(nd * 2, cl, (cl + cr) / 2, tp);
		build(nd * 2 + 1, (cl + cr) / 2 + 1, cr, tp);
	}
}

ll lz[200005 * 4][2];

void prop(int nd, int cl, int cr, int tp){
	if(lz[nd][tp]){
		st[nd][tp].first += lz[nd][tp];
		if(cl != cr){
			lz[nd * 2][tp] += lz[nd][tp];
			lz[nd * 2 + 1][tp] += lz[nd][tp];
		}
		lz[nd][tp] = 0;
	}
}

void upd(int nd, int cl, int cr, int l, int r, ll vv, int tp){
	prop(nd, cl, cr, tp);
	if(cr < l || r < cl) return;
	if(l <= cl && cr <= r){
		lz[nd][tp] += vv;
		prop(nd, cl, cr, tp);
		return;
	}

	upd(nd * 2, cl, (cl + cr) / 2, l, r, vv, tp);
	upd(nd * 2 + 1, (cl + cr) / 2 + 1, cr, l, r, vv, tp);
	st[nd][tp] = min(st[nd * 2][tp], st[nd * 2 + 1][tp]);
}

ll que(int nd, int cl, int cr, int l, int r, int tp){
	prop(nd, cl, cr, tp);
	if(cr < l || r < cl) return inf;
	if(l <= cl && cr <= r) return st[nd][tp].first;

	return min(que(nd * 2, cl, (cl + cr) / 2, l, r, tp), que(nd * 2 + 1, (cl + cr) / 2 + 1, cr, l, r, tp));
}

void update(int l, int r, ll vv, int tp){
	if(l <= r)
		upd(1, 0, n - 1, l, r, vv, tp);
	else{
		upd(1, 0, n - 1, l, n - 1, vv, tp);
		upd(1, 0, n - 1, 0, r, vv, tp);
	}
}

int kk;
vector<int> pref;

void init(int k, vector<int> r){
	n = r.size();
	pref.resize(n + 1);
	for(int i = 0; i < n; i ++)
		pref[i + 1] = pref[i] + r[i];
	kk = k;
	if(kk == 2) return;

	build(1, 0, n - 1, 0);build(1, 0, n - 1, 1);
//	exit(0);
	for(int i = 0; i < n; i ++){
		update(i, i, r[i], 0);
		update(i, i, r[i], 1);
	}

	while(st[1][1].first == 0){
		int ps = st[1][1].second;
		update(ps, ps, inf, 1);
		update((ps + 1) % n, (ps + (k - 1)) % n, 1, 0);
	}

	for(int vv = n; vv > 0; vv --){
		int id = st[1][0].second;
		arr[id] = vv;

		update((id + 1) % n, (id + (k - 1)) % n, -1, 0);
		update((id + n - (k - 1)) % n, (id + n - 1) % n, -1, 0);
		update((id + n - (k - 1)) % n, (id + n - 1) % n, -1, 1);

		while(st[1][1].first == 0){
			int ps = st[1][1].second;
			update(ps, ps, inf, 1);
			update((ps + 1) % n, (ps + (k - 1)) % n, 1, 0);
		}

		update(id, id, inf, 0);
	}
}

int compare_plants(int x, int y){
	if(kk == 2){
		if(pref[y] == pref[x]) return 1;
		if(pref[y] - pref[x] == y - x) return -1;
		if(pref[n] - (pref[y] - pref[x]) == n - (y - x)) return 1;
		if(pref[n] == (pref[y] - pref[x])) return -1;
		return 0;
	}
	if(arr[x] < arr[y]) return -1;
	return 1;
}

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