Submission #787984

#	Time	Username	Problem	Language	Result	Execution time	Memory
787984		GusterGoose27	Horses (IOI15_horses)	C++17	37 / 100	273 ms	51040 KiB

horses

#include "horses.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5+5;
const int inf = 1e9+5;
const int MOD = 1e9+7;

typedef long long ll;

int expo(ll a, int b) {
	ll cur = 1;
	while (b) {
		if (b & 1) {
			cur = (cur*a)%MOD;
		}
		a = (a*a)%MOD;
		b /= 2;
	}
	return cur;
}

int inv(int a) {
	return (a == 1) ? 1 : expo(a, MOD-2);
}

int mx[2*MAXN];
int x[MAXN];
int y[MAXN];
int xinv[MAXN];
int n;

class stree { // range max
public:
	stree() {
		for (int i = n; i < 2*n; i++) mx[i] = y[i-n];
		for (int i = n-1; i > 0; i--) mx[i] = max(mx[2*i], mx[2*i+1]);
	}
	void upd(int p, int v) {
		for (p += n, mx[p] = v; p > 1; p /= 2) {
			mx[p/2] = max(mx[p], mx[p^1]);
		}
	}
	int range_mx(int l, int r) {
		int ans = 0;
		for (l += n, r += n; r > l; r >>= 1, l >>= 1) {
			if (l & 1) ans = max(ans, mx[l++]);
			if (r & 1) ans = max(ans, mx[--r]);
		}
		return ans;
	}
};

stree *tree;
set<int> big;
ll prod = 1;

int solve() {
	ll req = 0; // how big of a value you need to see for it to be worth it
	ll ans = 0;
	ll cur_mult = prod;
	for (auto it = big.rbegin(); it != big.rend() && req < inf; it++) {
		int v = *it;
		int cur_mx = tree->range_mx(v, n);
		if (cur_mx > req) ans = (cur_mult*cur_mx)%MOD;
		req = max(req, (ll)cur_mx);
		req *= x[v];
		cur_mult = (cur_mult*xinv[v])%MOD;
	}
	if (mx[1] > req) return mx[1];
	return ans;
}

int init(int N, int X[], int Y[]) {
	n = N;
	for (int i = 0; i < n; i++) {
		x[i] = X[i];
		y[i] = Y[i];
		if (x[i] > 1) {
			big.insert(i);
			xinv[i] = inv(x[i]);
		}
		prod = (prod*x[i])%MOD;
	}
	tree = new stree();
	return solve();
}

int updateX(int pos, int val) {	
	prod = (prod*xinv[pos])%MOD;
	big.erase(pos);
	x[pos] = val;
	xinv[pos] = inv(x[pos]);
	prod = (prod*x[pos])%MOD;
	if (x[pos] > 1) big.insert(pos);
	return solve();
}

int updateY(int pos, int val) {
	y[pos] = val;
	tree->upd(pos, val);
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'int expo(ll, int)':
horses.cpp:22:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   22 |  return cur;
      |         ^~~
horses.cpp: In function 'int solve()':
horses.cpp:73:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   73 |  return ans;
      |         ^~~

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