제출 #1186319

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186319		jasonic	말 (IOI15_horses)	C++20	17 / 100	244 ms	101944 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

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

    /*
    
    v: best range product in log 10
    rv: full range product
    bsY: the value of Y (in base 10) that maximizes answer

    prod: best range product
    rprod: full range product
    ans: the answer for this range

    bsY_nolog: i think u can understand that

    */

    void combine() {
        if(lt->v + lt->bsY > lt->rv + rt->v + rt->bsY) { // answer is better on the left
            v = lt->v;
            prod = lt->prod;
            bsY = lt->bsY;
            ans = lt->ans;
            bsY_nolog = lt->bsY_nolog;
        } else {
            v = lt->rv + rt->v;
            prod = ((lt->rprod * rt->prod) % MOD + MOD) % MOD;
            bsY = rt->bsY;
            ans = ((lt->rprod * rt->ans) % MOD + MOD) % MOD;
            bsY_nolog = rt->bsY_nolog;
        }
        rv = lt->rv + rt->rv;
        rprod = ((lt->rprod * rt->rprod) % MOD + MOD) % MOD;
    }

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

    ST(int bl, int br, vector<int> &X, vector<int> &Y) {
        lt = rt = nullptr;
        v = rv = 0;
        l = bl; r = br;
        prod = rprod = 0;
        bsY = -1;
        ans = -1;

        if(l == r) {
            v = rv = X[l]==1?0:log10(X[l]);
            prod = rprod = X[l];
            bsY = Y[l]==1?0:log10(Y[l]);
            bsY_nolog = Y[l];
            ans = ((X[l] * Y[l]) % MOD + MOD) % MOD;
        } else {
            ll m = (l+r)>>1;
            lt = new ST(l, m, X, Y);
            rt = new ST(m+1, r, X, Y);

            combine();
        }
    }

    ll qryAns() {
        return ans;
    }

    void updX(ll i, ll x) {
        if(i < l || r < i) return;
        if(l == r && r == i) {
            v = rv = x==1?0:log10(x);
            prod = rprod = x;
            ans = ((x * bsY_nolog) % MOD + MOD) % MOD;

            return;
        }

        lt->updX(i, x);
        rt->updX(i, x);
        combine();
    }

    void updY(ll i, ll y) {
        if(i < l || r < i) return;
        if(l == r && r == i) {
            bsY = y==1?0:log10(y);
            bsY_nolog = y;
            ans = ((prod * y) % MOD + MOD) % MOD;

            return;
        }

        lt->updY(i, y);
        rt->updY(i, y);
        combine();

    }
};

ST tree;

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

    tree = ST(0, N-1, x, y);

    return tree.qryAns();
}

ll updateX(int i, int v) {
    tree.updX(i, v);
    
    return tree.qryAns();
}

ll updateY(int i, int v) {
    tree.updY(i, v);

    return tree.qryAns();
}

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