Submission #38867

#	Time	Username	Problem	Language	Result	Execution time	Memory
38867		14kg	Horses (IOI15_horses)	C++11	17 / 100	496 ms	19268 KiB

horses

#include "horses.h"
#define MOD 1000000007
#define N 500001
#define NN 1048576

struct NUM {
	bool big_num;
	int num;
	void push(bool _big_num, int _num) {
		big_num = _big_num, num = _num;
	}
} tree1[NN], one;
int n, nn, tree2[NN], Y[N];

NUM mul(NUM x, NUM y) {
	long long tx = x.num, ty = y.num, temp = (tx*ty) % MOD;
	NUM res;

	res.push(tx*ty >= MOD, (int)temp);
	return res;
}
long long ll_mul(long long x, long long y) {
	return x*y;
}

NUM get_tree1(int lev, int l, int r, int x, int y) {
	int mid = (l + r) / 2;

	if (x <= l && r <= y) return tree1[lev];
	if (r < x || y < l) return one;
	return mul(get_tree1(lev * 2, l, mid, x, y), get_tree1(lev * 2 + 1, mid + 1, r, x, y));
}
void tree1_update(int lev) {
	tree1[lev] = mul(tree1[lev * 2], tree1[lev * 2 + 1]);

	if (lev > 1) tree1_update(lev / 2);
}
void tree2_update(int lev) {
	int l = lev * 2, r = lev * 2 + 1;
	NUM temp = get_tree1(1, 1, nn, tree2[l] + 1, tree2[r]);

	if (temp.big_num || (long long)Y[tree2[l]] <= ll_mul(temp.num, Y[tree2[r]])) tree2[lev] = tree2[r];
	else tree2[lev] = tree2[l];

	if (lev > 1) tree2_update(lev / 2);
}
int output() {
	long long out = ll_mul(get_tree1(1, 1, nn, 1, tree2[1]).num, Y[tree2[1]]);
	return (int)(out%MOD);
}

int init(int _n, int *in_x, int *in_y) {
	NUM temp;

	n = _n, one.push(false, 1);
	for (nn = 1; nn < n; nn *= 2);
	for (int i = 0; i < n; i++) {
		tree1[nn + i].push(false, in_x[i]);
		tree2[nn + i] = i + 1;
		Y[i + 1] = in_y[i];
	}

	for (int i = nn - 1; i >= 1; i--) tree1[i] = mul(tree1[i * 2], tree1[i * 2 + 1]);
	for (int i = nn - 1; i >= 1; i--) {
		int l = i * 2, r = i * 2 + 1;
		temp = get_tree1(1, 1, nn, tree2[l] + 1, tree2[r]);

		if (temp.big_num || (long long)Y[tree2[l]] <= ll_mul(temp.num, Y[tree2[r]])) tree2[i] = tree2[r];
		else tree2[i] = tree2[l];
	}

	return output();
}
int updateX(int pos, int val) {	
	tree1[nn + pos].push(false, val);
	tree1_update((nn + pos) / 2), tree2_update((nn + pos) / 2);
	return output();
}
int updateY(int pos, int val) {
	Y[pos + 1] = val;
	tree2_update((nn + pos) / 2);
	return output();
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23