Submission #1189726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189726		jasonic	Horses (IOI15_horses)	C++20	17 / 100	148 ms	91376 KiB

horses

/*

otherside technique!!

instead of storing the value of log(x_i) + log(y_i), store log(prefix sum of x_i) + log(y_i)

although the problem now becomes lazy prop, i think its much easier to code it this way

*/

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

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
#define MOD 1000000007

double prefXLog[500005];
double xLog[500005];
double yLog[500005];
ll x[500005];
ll y[500005];
ll prefAns[500005];

ll modpow(ll b, ll e) {
    if(e == 0) return 1;
    else if(e&1) return (b * modpow(b, e-1))%MOD;
    else return modpow((b*b) % MOD, e/2);
}

ll modinv(ll b) {
    return modpow(b, MOD-2);
}

struct ST{
    double sum;
    ll ans;

    ST *lt, *rt;
    int l, r;
    double lz;
    ll lz2;

    void prop() {
        if(lz == 0) return;
        sum += lz;
        ans = (ans * lz2) % MOD;

        if(lt) {
            lt->lz += lz;
            rt->lz += lz;

            lt->lz2 *= lz2;
            rt->lz2 *= lz2;
            lt->lz2 %= MOD;
            rt->lz2 %= MOD;
        }
        lz = double(0.0);
        lz2 = 1;
    }

    void comb() {
        if(lt->sum > rt->sum) {
            sum = lt->sum;
            ans = lt->ans;
        } else {
            sum = rt->sum;
            ans = rt->ans;
        }
    }

    ST() {
        sum = lz = double(0.0);
        ans = 0;
        lz2 = 1;
        l = r = -1;
        lt = rt = nullptr;
    }

    ST(ll bl, ll br) {
        l = bl; r = br;
        lt = rt = nullptr;
        sum = lz = double(0.0);
        ans = 0;
        lz2 = 1;

        if(l == r) {
            sum = prefXLog[l] + yLog[l];
            ans = prefAns[l];
        } else {
            ll m = (l+r)>>1;
            lt = new ST(l, m);
            rt = new ST(m+1, r);
            comb();
        }
    }

    ll qry() {
        return ans;
    }

    void updX(ll ql, ll qr, ll v) {
        prop();
        if(qr < l || r < ql) return;
        if(l <= ql && qr <= r) {
            // ql is the left position
            lz += log10(v) - xLog[ql];
            lz2 *= v;
            lz2 *= modinv(x[ql]);
            lz2 %= MOD;
            prop();
            return;
        }
        lt->updX(ql, qr, v);
        rt->updX(ql, qr, v);
        comb();
    };

    void updY(ll i, ll v) {
        if(i < l || r < i) return;
        if(l == r && i == r) {
            lz += log10(v) - yLog[i];
            lz2 *= v;
            lz2 *= modinv(y[i]);
            lz2 %= MOD;
            prop();
            return;
        }
        lt->updY(i, v);
        rt->updY(i, v);
        comb();
    }
};

ST tree;
ll n;

ll init (int N, int X[], int Y[]){
    n = N;
    for(int i = 0; i < N; i++) {
        x[i] = X[i];
        xLog[i] = log10(X[i]);
        prefXLog[i] = log10(X[i]);
        prefAns[i] = X[i];
        if(i) {
            prefXLog[i] += prefXLog[i-1];
            prefAns[i] = ((prefAns[i] * prefAns[i-1]) % MOD + MOD) % MOD;
        }
    }
    for(int i = 0; i < N; i++) {
        y[i] = Y[i];
        yLog[i] = log10(Y[i]);
        prefAns[i] *= Y[i];
        prefAns[i] %= MOD;
        prefAns[i] += MOD;
        prefAns[i] %= MOD;
    }

    tree = ST(0, N-1);

    return tree.qry();
}

ll updateX (int pos, int val) {
    tree.updX(pos, n-1, (ll)val);
    x[pos] = val;
    xLog[pos] = log10(val);
    return tree.qry();
}

ll updateY (int pos, int val) {
    tree.updY(pos, (ll)val);
    y[pos] = val;
    yLog[pos] = log10(val);
    return tree.qry();
}

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