Submission #38866

#	Time	Username	Problem	Language	Result	Execution time	Memory
38866		14kg	Horses (IOI15_horses)	C++11	17 / 100	183 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));
}

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];
	}

	long long out = ll_mul(get_tree1(1, 1, nn, 1, tree2[1]).num, Y[tree2[1]]);
	return (int)(out%MOD);
}

int updateX(int pos, int val) {	
	return 0;
}

int updateY(int pos, int val) {
	return 0;
}

Compilation message (stderr)

horses.cpp:58:17: warning: unused parameter 'pos' [-Wunused-parameter]
 int updateX(int pos, int val) { 
                 ^
horses.cpp:58:26: warning: unused parameter 'val' [-Wunused-parameter]
 int updateX(int pos, int val) { 
                          ^
horses.cpp:62:17: warning: unused parameter 'pos' [-Wunused-parameter]
 int updateY(int pos, int val) {
                 ^
horses.cpp:62:26: warning: unused parameter 'val' [-Wunused-parameter]
 int updateY(int pos, int val) {
                          ^

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