Submission #229607

#	Time	Username	Problem	Language	Result	Execution time	Memory
229607		mieszko11b	Horses (IOI15_horses)	C++14	100 / 100	321 ms	55184 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll MOD = ll(1e9) + 7;

ll pot(ll a, ll b) {
	if(b == 0)
		return 1;
	if(b % 2)
		return pot(a, b - 1) * a % MOD;
	ll tmp = pot(a, b / 2);
	return tmp * tmp % MOD;
}

ll inv(ll x) {
	return pot(x, MOD - 2);
}

struct SegmentTree {
	int lv;
	int d[1100007];
	
	SegmentTree(int n) {
		lv = 2;
		while(lv < n + 2)
			lv *= 2;
	}
	
	void insert(int i, int v) {
		int w = i + lv;
		d[w] = v;
		w /= 2;
		while(w) {
			d[w] = max(d[2 * w], d[2 * w + 1]);
			w /= 2;
		}
	}
	
	int query(int a, int b) {
		if(a > b) return 0;
		int va = a + lv;
		int vb = b + lv;
		int res = max(d[va], d[vb]);
		while(va / 2 != vb/  2) {
			if(va % 2 == 0)
				res = max(res, d[va + 1]);
			if(vb % 2 == 1)
				res = max(res, d[vb - 1]);
			va /= 2;
			vb /= 2;
		}
		return res;
	}
	
	void recalc() {
		for(int i = lv - 1 ; i >= 1 ; i--)
			d[i]  = max(d[2 * i], d[2 * i + 1]);
	}
};

int n;
int x[500007], y[500007];
ll all = 1;
int prv[500007], nxt[500007];
int max_to_nxt[500007];
set<int> S;
SegmentTree ST(500007);

int calc() {
	int i = *prev(S.end());
	ll pro = x[i];
	while(pro <= ll(1e9) && i > 0) {
		i = prv[i];
		pro *= x[i];
	}
	ll pref = all * inv(pro % MOD) % MOD * x[i] % MOD;
	ll local_res = 0, res;
	ll mul = 1;
	while(true) {
		ll a = mul * max_to_nxt[i];
		if(a > local_res) {
			local_res = a;
			res = a % MOD * pref % MOD;
		}
		if(!nxt[i])
			break;
		i = nxt[i];
		mul *= x[i];
	}
	
	return res % MOD;
}

int init(int N, int X[], int Y[]) {
	n = N;
	int lst = -1;
	int maxv = 0;
	for(int i = 0 ; i < n ; i++) {
		x[i] = X[i];
		//~ x1[i] = 1;
		y[i] = Y[i];
		if(x[i] > 1 || i == 0) {
			prv[i] = lst;
			if(lst != -1) {
				nxt[lst] = i;
				max_to_nxt[lst] = maxv;
			}
			maxv = 0;
			all *= x[i];
			all %= MOD;
			//~ x1[i] = inv(x[i]);
			lst = i;
			S.insert(i);
		}
		maxv = max(maxv, y[i]);
		ST.d[ST.lv + i] = y[i];
	}
	max_to_nxt[lst] = maxv;
	ST.recalc();
	
	return calc();
}

void remove_special(int pos) {
	if(pos == 0) return ;
	
	auto it = S.lower_bound(pos);
	int i1 = *prev(it);
	int i2 = 0;
	if(next(it) != S.end())
		i2 = *next(it);
	
	S.erase(pos);
	nxt[i1] = i2;
	if(i2) {
		prv[i2] = i1;
		max_to_nxt[i1] = ST.query(i1, i2 - 1);
	} else
		max_to_nxt[i1] = ST.query(i1, n - 1);
}

void add_special(int pos) {
	if(pos == 0) return ;
	
	auto it = S.lower_bound(pos);
	int i2 = 0;
	if(it != S.end())
		i2 = *it;
	int i1 = *prev(it);
	
	S.insert(pos);
	nxt[i1] = pos;
	nxt[pos] = i2;
	prv[pos] = i1;
	if(i2)
		prv[i2] = pos;
	max_to_nxt[i1] = ST.query(i1, pos - 1);
	if(i2)
		max_to_nxt[pos] = ST.query(pos, i2 - 1);
	else
		max_to_nxt[pos] = ST.query(pos, n - 1);
}

int updateX(int pos, int val) {	
	all = all * inv(x[pos]) % MOD * val % MOD;
	
	if(x[pos] == 1 && val > 1) {
		x[pos] = val;
		add_special(pos);
	} else if(x[pos] > 1 && val == 1) {
		x[pos] = val;
		remove_special(pos);
	} else
		x[pos] = val;
	
	return calc();
}

int updateY(int pos, int val) {
	y[pos] = val;
	ST.insert(pos, val);
	auto it = S.upper_bound(pos);
	int i = *prev(it);
	if(nxt[i])
		max_to_nxt[i] = ST.query(i, nxt[i] - 1);
	else
		max_to_nxt[i] = ST.query(i, n - 1);
	
	return calc();
}

Compilation message (stderr)

horses.cpp: In function 'int calc()':
horses.cpp:95:13: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  return res % MOD;
         ~~~~^~~~~
horses.cpp:95:15: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return res % MOD;
               ^~~

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