Submission #206566

#	Time	Username	Problem	Language	Result	Execution time	Memory
206566		spdskatr	Horses (IOI15_horses)	C++14	100 / 100	289 ms	41320 KiB

horses

#include "horses.h"
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <utility>
#define MOD 1000000007
#define SZ (1<<19)
using namespace std;
typedef long long ll;
ll mulst[1<<20], ansst[1<<20];
int x[1<<19], y[1<<19];

// Segtree stores best year to sell horses in range
int st[1<<20];

ll mulover(ll a, ll b) {
	if (a == -1 || b == -1) return -1;
	if (a * b > 1000000000) return -1;
	return a*b;
}

ll prod(int l, int r) {
	ll res = 1;
	for (l += SZ, r += SZ; res != -1 && l < r; l >>= 1, r >>= 1) {
		if (l&1) res = mulover(res, mulst[l++]);
		if (r&1) res = mulover(res, mulst[--r]);
	}
	return res;
}

ll prodans(int l, int r) {
	ll res = 1;
	for (l += SZ, r += SZ; l < r; l >>= 1, r >>= 1) {
		if (l&1) res = (res * ansst[l++]) % MOD;
		if (r&1) res = (res * ansst[--r]) % MOD;
	}
	return res;
}

int stc(int i, int j) {
	if (j > 1000000000) return i;
	//printf("stc(%d, %d)\n", i, j);
	assert(i <= j);
	ll val = mulover(prod(i+1, j+1), y[j]);
	if (val == -1 || val > y[i]) {
		return j;
	}
	return i;
}

int init(int N, int X[], int Y[]) {
	for (int i = 0; i < N; i++) {
		x[i] = X[i];
		y[i] = Y[i];
		mulst[i+SZ] = ansst[i+SZ] = x[i];
		st[i+SZ] = i;
	}
	for (int i = N; i < SZ; i++) {
		st[i+SZ] = 2069696969;
	}
	for (int i = SZ-1; i > 0; i--) {
		mulst[i] = mulover(mulst[i<<1], mulst[i<<1|1]);
		ansst[i] = (ansst[i<<1] * ansst[i<<1|1]) % MOD;
	}
	for (int i = SZ-1; i > 0; i--) {
		st[i] = stc(st[i<<1], st[i<<1|1]);
	}
	//printf("Optimal position: %d\n", st[1]);
	return (int)((prodans(0, st[1]+1) * y[st[1]]) % MOD);
}

int updateX(int pos, int val) {	
	x[pos] = val;
	int i = pos + SZ;
	mulst[i] = val;
	ansst[i] = val;
	for (int j = i; j > 1; j >>= 1) {
		mulst[j>>1] = mulover(mulst[j], mulst[j^1]);
		ansst[j>>1] = (ansst[j] * ansst[j^1]) % MOD;
	}
	i >>= 1;
	for (; i > 0; i >>= 1) {
		st[i] = stc(st[i<<1], st[i<<1|1]);
	}
	//printf("Optimal position: %d\n", st[1]);
	return (int)((prodans(0, st[1]+1) * y[st[1]]) % MOD);
}

int updateY(int pos, int val) {
	y[pos] = val;
	int i = pos + SZ;
	i >>= 1;
	for (; i > 0; i >>= 1) st[i] = stc(st[i<<1], st[i<<1|1]);
	//printf("Optimal position: %d\n", st[1]);
	return (int)((prodans(0, st[1]+1) * y[st[1]]) % MOD);
}

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