Submission #1190180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190180		jasonic	Horses (IOI15_horses)	C++20	54 / 100	494 ms	107040 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)

const ll MOD = 1e9 + 7;
double prefXLog[500005]; // ued only once lol
ll prefAns[500005];

double xLog[500005];
double yLog[500005];
ll x[500005];
ll y[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 + MOD) % MOD, e/2);
}

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

struct ST{
    double sum;
    ll ans, idx;

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

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

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

            lt->lz2 = ((lt->lz2 * lz2) % MOD + MOD) % MOD;
            rt->lz2 = ((rt->lz2 * lz2) % MOD + MOD) % MOD;

            lt->welazy = true;
            rt->welazy = true;
        }
        welazy = false;
        lz = double(0.0);
        lz2 = 1;
    }

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

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

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

        if(l == r) {
            sum = prefXLog[l] + yLog[l];
            ans = prefAns[l];
            idx = 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(ql <= l && r <= qr) {
            // ql is the left position
            welazy = true;
            lz += log10(v) - xLog[ql];
            lz2 = ((lz2 * v) % MOD + MOD) % MOD;
            lz2 = ((lz2 * modinv(x[ql])) % MOD + MOD) % MOD;
            prop();
            return;
        }
        lt->updX(ql, qr, v);
        rt->updX(ql, qr, v);
        comb();
    };

    void updY(ll i, ll v) {
        prop();
        if(i < l || r < i) return;
        if(l == r && i == r) {
            welazy = true;
            lz2 = ((lz2 * modinv(y[i])) % MOD + MOD) % MOD; // remove the previous factor
            lz2 = ((lz2 * v) % MOD + MOD) % MOD; // add the new factor
            lz += log10(v) - yLog[i];
            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] = ((prefAns[i] * Y[i]) % MOD + MOD) % 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: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23