제출 #1190961

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190961		jasonic	말 (IOI15_horses)	C++20	17 / 100	314 ms	117764 KiB

horses

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;
#define REP(a,i,n) for (ll i=a;i<n;i++)
#define ll long long
#define ssize 500'005
#define ld long double

const ll MOD = 1e9+7;
int N;
ll eks[ssize];
ll X[ssize], Y[ssize];

ll bin_exp(ll a, ll b) {
    if (b == 0) return 1;
    if (b % 2) return (bin_exp(a, b - 1) * a) % MOD;
    ll res = bin_exp(a, b >> 1);
    return (res * res) % MOD;
}

ll inv(ll a) {
    return bin_exp(a, MOD - 2);
}

struct SegTree{
    ll l, r, real, rLazy;
    SegTree *lt, *rt;
    ld lazy, val;

    void combine(){
        if (lt->val > rt->val) {
            val = lt->val;
            real = lt->real;
            return;
        }
        val = rt->val;
        real = rt->real;
    }

    SegTree(ll left, ll right, ll thing[], vector<ld> &a){
        l = left;
        r = right;
        lt = rt = nullptr;
        lazy = 0, rLazy = 1;

        if(left == right){
            val = a[left];
            real = thing[left];
            return;
        }

        ll mid = (l+r)>>1;
        lt = new SegTree(l, mid, thing, a);
        rt = new SegTree(mid+1,r, thing, a);
        combine();
    }

    void propagate(){
        if(lazy || rLazy!=1){
            val += lazy * ((ld)(r - l + 1));
            real = (real*rLazy)%MOD;
            if(lt) {
                lt->lazy += lazy;
                lt->rLazy = (lt->rLazy*rLazy)%MOD;
            }
            if(rt) {
                rt->lazy += lazy;
                rt->rLazy = (rt->rLazy*rLazy)%MOD;
            }
        }
        lazy = 0;
        rLazy = 1;
    }

    void update(ll ul, ll ur, ll newX, ld logged){
        propagate();
        if(ul > r || ur < l){
            return;
        }

        if(ul <= l && r <= ur){
            lazy += logged;
            rLazy = (rLazy*newX)%MOD;
            propagate();
            return;
        }

        lt->update(ul,ur,newX, logged);
        rt->update(ul,ur,newX, logged);
        combine();
    }

    pair<ld, ll> query(ll ql, ll qr){
        propagate();
        if(ql > r || qr < l){
            return {-MOD, 0};
        }

        if(ql <= l && r <= qr){
            return {val, real};
        }

        return max(lt->query(ql,qr), rt->query(ql,qr));
    }

    ll solve() {
        pair<ld, ll> pa = query(0, N-1);
        return pa.second;
    }
};

SegTree *st;
ll init(int n, int x[], int y[]) {
    N = n;
    REP(0,i,n) {
        X[i] = x[i]; Y[i] = y[i];
    }

    vector<ld> a(1, log10(x[0]));
    eks[0] = x[0];
    REP(1,i,n) {
        a.push_back(a.back()+log10(X[i])); //prefsum of log10 x
        eks[i] = (eks[i-1]*X[i])%MOD;
    }

    REP(0, i, n) {
        eks[i] = (eks[i]*Y[i])%MOD;
        a[i] += log10(Y[i]);
    }

    st = new SegTree(0, N-1, eks, a); //a is log10 version of eks. its pref sum + y values
    return st->solve();
}

ll updateX(int pos, int val) {
    ll v = val;
    st->update(pos, N-1, inv(X[pos]), -log10(X[pos])); // remove old value
    st->update(pos, N-1, v, log10(v)); // new val
    X[pos] = v; // mark new val
    return st->solve();
}

ll updateY(int pos, int val) {
    ll v = val;
    st->update(pos, pos, inv(Y[pos]), -log10(Y[pos]));
    st->update(pos, pos, v, log10(v));
    Y[pos] = v;
    return st->solve();
}

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