Submission #1310072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310072		muhammad-ahmad	Horses (IOI15_horses)	C++20	0 / 100	121 ms	66956 KiB

horses

#include <bits/stdc++.h>
using namespace std;

#include "horses.h"

const long long N = 5e5 + 5, M = 1e9 + 7;
long long n, cur, x[N], y[N];

struct node {
    long long mxy = 0, px = 1;
    long long left = -1, right = -1;
};

vector<node> T;
set<long long> st;

node join(node a, node b) {
    node ans;
    ans.px = (a.px * b.px) % M;
    ans.mxy = max(a.mxy, b.mxy);
    return ans;
}

void build(long long v = 0, long long s = 0, long long e = n) {
    if (e - s == 1) {
        T[v].mxy = y[s];
        T[v].px = x[s] % M;
        return;
    }
    T[v].left = ++cur;
    T[v].right = ++cur;
    long long lc = T[v].left, rc = T[v].right, mid = (s + e) / 2;
    build(lc, s, mid);
    build(rc, mid, e);
    T[v] = join(T[lc], T[rc]);
}

node query(long long l, long long r, long long v = 0, long long s = 0, long long e = n) {
    if (l <= s && e <= r) return T[v];
    long long mid = (s + e) / 2, lc = T[v].left, rc = T[v].right;
    if (r <= mid) return query(l, r, lc, s, mid);
    if (l >= mid) return query(l, r, rc, mid, e);
    return join(query(l, r, lc, s, mid), query(l, r, rc, mid, e));
}

void updx(long long pos, long long val, long long v = 0, long long s = 0, long long e = n) {
    if (e - s == 1) {
        T[v].px = val % M;
        return;
    }
    long long mid = (s + e) / 2, lc = T[v].left, rc = T[v].right;
    if (pos < mid) updx(pos, val, lc, s, mid);
    else updx(pos, val, rc, mid, e);
    T[v] = join(T[lc], T[rc]);
}

void updy(long long pos, long long val, long long v = 0, long long s = 0, long long e = n) {
    if (e - s == 1) {
        T[v].mxy = val;
        return;
    }
    long long mid = (s + e) / 2, lc = T[v].left, rc = T[v].right;
    if (pos < mid) updy(pos, val, lc, s, mid);
    else updy(pos, val, rc, mid, e);
    T[v] = join(T[lc], T[rc]);
}

int solve() {
    vector<long long> cands;
    cands.push_back(0); 

    if (!st.empty()) {
        auto it = st.end(); it--;
        vector<long long> last_growth;
        long long pd = 1;
        for (int i = 0; i < 32; i++) {
            last_growth.push_back(*it);
            pd *= x[*it];
            if (it == st.begin() || pd > 2e9) break;
            it--;
        }
        reverse(last_growth.begin(), last_growth.end());
        for (long long idx : last_growth) {
            if (idx != 0) cands.push_back(idx);
        }
    }
    
    sort(cands.begin(), cands.end());
    cands.erase(unique(cands.begin(), cands.end()), cands.end());

    long long best = cands[0];
    for (size_t i = 1; i < cands.size(); i++) {
        long long curr = cands[i];
        long long growth = 1;
        for (long long k = best + 1; k <= curr; k++) {
            growth *= x[k];
            if (growth > 1e9) break;
        }
        
        long long nxt = (i + 1 < cands.size() ? cands[i + 1] : n);
        long long cy = query(curr, nxt).mxy;
        long long by = query(best, curr).mxy;
        
        if (growth > 1e9 || growth * cy >= by) best = curr;
    }

    long long px = query(0, best + 1).px;
    long long ed = n;
    auto nit = st.upper_bound(best);
    if (nit != st.end()) ed = *nit;
    
    long long my = query(best, ed).mxy;
    return (int)((px * my) % M);
}

int init(int N_val, int X[], int Y[]) {
    n = N_val; cur = 0; st.clear();
    for (int i = 0; i < n; i++) {
        x[i] = X[i]; y[i] = Y[i];
        if (x[i] > 1) st.insert(i);
    }
    T.assign(2 * n + 10, node());
    build();
    return solve();
}

int updateX(int pos, int val) {
    if (x[pos] > 1) st.erase(pos);
    x[pos] = val;
    if (x[pos] > 1) st.insert(pos);
    updx(pos, val);
    return solve();
}

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

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