제출 #1190881

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190881		pensive	Horses (IOI15_horses)	C++20	17 / 100	333 ms	125624 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];
ld 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 X[], vector<ld> &a){
        l = left;
        r = right;
        lt = rt = nullptr;
        lazy = 0, rLazy = 1;

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

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

    void propagate(){
        if(lazy){
            val += lazy * ((ld)(r - l + 1));
            real = (real*rLazy)%MOD;
            if(lt) lt->lazy += lazy;
            if(rt) rt->lazy += lazy;
        }
        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));
    }

    ld solve() {
        return query(0, N-1).second;
    }
};

SegTree *st;
ll init(int n, int x[], int y[]) {
    N = n;
    vector<ld> a;
    a.push_back(log10(x[0]));
    eks[0] = x[0];
    REP(1,i,n) {
        a.push_back(a.back()+log10(x[i]));
        eks[i] = (eks[i-1]*((ll)x[i]))%MOD;
    }
    REP(0, i, n) {
        eks[i] = (eks[i]*((ll)y[i]))%MOD;
        a[i] += log10(y[i]);
        X[i] = x[i]; Y[i] = y[i];
    }
    st = new SegTree(0, N-1, eks, a);
    return st->solve();
}

ll updateX(int pos, int val) {
    ll v = val;
    st->update(pos, N-1, (val*inv(X[pos]))%MOD, log10(val) - log10(X[pos]));
    X[pos] = val;
    return st->solve();
}

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

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