Submission #1190230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190230		jasonic	Horses (IOI15_horses)	C++20	17 / 100	92 ms	91408 KiB

horses

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

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

ll x[500005];
ll y[500005];

struct ST{
    double v, rv;
    ll rprod, ans;
    ST *lt, *rt;
    ll l, r;

    void comb() {
        rv = lt->rv + rt->rv;
        rprod = ((lt->rprod * rt->rprod) % MOD + MOD) % MOD;
        if(lt->v > lt->rv + rt->v) {
            v = lt->v;
            ans = lt->ans;
        } else {
            v = lt->rv + rt->v;
            ans = ((lt->rprod * rt->ans) % MOD + MOD) % MOD;
        }
    }

    ST() {
        l = r = -1;
        v = rv = double(0.0);
        lt = rt = nullptr;
        rprod = ans = 0;
    }

    ST(int bl, int br) {
        l = bl; r = br;
        v = rv = double(0.0);
        lt = rt = nullptr;

        if(l == r) {
            rprod = x[l];
            ans = ((x[l] * y[l]) % MOD + MOD) % MOD;
            v = log10(ans), rv = log10(rprod);
        } else {
            int m = (l+r)/2;
            lt = new ST(l, m);
            rt = new ST(m+1, r);
            comb();
        }
    }

    void updX(int i, ll v) {
        if(i < l || r < i) return;
        if(l == r && r == i) {
            rprod = x[l];
            ans = ((x[l] * y[l]) % MOD + MOD) % MOD;
            rv = log10(x[l]), v = rv + log10(y[l]);
        } else {
            lt->updX(i, v);
            rt->updX(i, v);
            comb();
        }
    }

    void updY(int i, ll v) {
        if(i < l || r < i) return;
        if(l == r && r == i) {
            ans = ((x[l] * y[l]) % MOD + MOD) % MOD;
            v = rv + log10(y[l]);
        } else {
            lt->updX(i, v);
            rt->updX(i, v);
            comb();
        }
    }
};

ST tree;

ll init(int N, int X[], int Y[]) {
    for(int i = 0; i < N; i++) x[i] = X[i];
    for(int i = 0; i < N; i++) y[i] = Y[i];
    // annoying

    tree = ST(0, N-1);

    return tree.ans;
}

ll updateX(int i, int v) {
    x[i] = v;
    tree.updX(i, v);
    
    return tree.ans;
}

ll updateY(int i, int v) {
    y[i] = v;
    tree.updY(i, v);

    return tree.ans;
}

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