Submission #1286555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286555		tschav_	Horses (IOI15_horses)	C++20	0 / 100	1594 ms	35640 KiB

horses

#include <bits/stdc++.h>
using namespace std;
using ll = unsigned long long;
vector<ll> x, y;
int n;
int m;
ll prod = 1;
int idx = -1;
set<int> st;
static const ll MOD = 1e9+7;

ll binpow(ll a, ll b, ll m) {
    a %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

ll gety(int id) {
    int m = st.size();
    if (id < 0 || id >= m) return 0;

    auto it = next(st.begin(), id); 
    int init = *it;
    int lim = n;

    if (id < m - 1) {
        auto it2 = next(it);
        lim = *it2;
    }

    ll mx = 0ll;
    for (int i = init; i < lim; ++i) {
        mx = max(mx, y[i]);
    }
    return mx;
}

ll solve() {
    ll mx = 0ll;
    if (idx != -1) mx = gety(idx);

    ll curr = 1;

    auto it = (idx + 1 < m) ? next(st.begin(), idx + 1) : st.end();
    for (int i = idx + 1; it != st.end(); ++i, ++it) {
        curr *= x[*it];
        ll G = gety(i);
        ll val = curr * G;
        if (val > mx) mx = val;
    }

    ll ans = mx % MOD;
    return (ans * (prod % MOD)) % MOD;
}

void ind() {
    idx = -1;
    ll P = 1ll;
    int i = m - 1;
    for (auto it = st.rbegin(); it != st.rend(); ++it, --i) {
        int pos = *it;
        if (P > 1e9 / x[pos]) {
            break;
        } else {
            P *= x[pos];
			idx = i;
        }
    }
}

void getprod() {
    prod = 1ll;
    if (idx < 0) return;
    auto it = st.begin();
    for (int i = 0; i <= idx and it != st.end(); ++i, ++it) {
        prod = (prod * (x[*it] % MOD)) % MOD;
    }
}

int init(int N, int X[], int Y[]) {
	n = N;
	x.resize(n,0ll);
	y.resize(n,0ll);
	for(int i = 0; i < n; ++i) {
		x[i] = X[i];
		y[i] = Y[i];
		if(x[i] >= 2){
			st.insert(i);
		}
	}
	m = st.size();

	ind();
	getprod();
	return int(solve());
}

int updateX(int pos, int val) {
	ll old = x[pos];
	x[pos] = val;

	if(val == 1 and old != 1) {
		st.erase(pos);
	}
	if(val != 1 and old == 1) {
        st.insert(pos);
	}
    m = st.size();

	ind();
	//int I = *(next(st.begin(),idx));
	// if(pos <= I) {
    //     prod = (prod * binpow(old, MOD-2,MOD)) % MOD;
    //     prod = (prod * val) % MOD;
	// }
	getprod();
	return int(solve());
}

int updateY(int pos, int val) {
	y[pos] = val;
	ind();
	return int(solve());
}

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