Submission #1281581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281581		nathlol2	Horses (IOI15_horses)	C++20	100 / 100	259 ms	122132 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5 + 5;
const ll MOD = 1000000007LL;
vector<ll> x(N), y(N);
int n;
struct lazyseg{
    pair<long double, int> seg[4*N];
    long double lazy[4*N];
    lazyseg(){
        for(int i = 0;i<4*N;i++){
            lazy[i] = 0.0L;
            seg[i] = {-INFINITY, 0};
        }
    }
    void push(int nd, int l, int r){
        if(fabsl(lazy[nd]) > 0.0L){
            seg[nd].first += lazy[nd];
            if(l != r){
                lazy[nd * 2] += lazy[nd];
                lazy[nd * 2 + 1] += lazy[nd];
            }
            lazy[nd] = 0.0L;
        }
    }
    void build_from_array(int nd, int l, int r, const vector<long double> &arr){
        if(l == r){
            seg[nd] = {arr[l], -l};
            return;
        }
        int md = (l + r) >> 1;
        build_from_array(nd*2, l, md, arr);
        build_from_array(nd*2+1, md+1, r, arr);
        seg[nd] = max(seg[nd*2], seg[nd*2+1]);
    }
    void upd(int nd, int l, int r, int ql, int qr, long double v){
        push(nd, l, r);
        if(r < ql || l > qr) return;
        if(ql <= l && r <= qr){
            lazy[nd] += v;
            push(nd, l, r);
            return;
        }
        int md = (l + r) >> 1;
        upd(nd*2, l, md, ql, qr, v);
        upd(nd*2+1, md+1, r, ql, qr, v);
        seg[nd] = max(seg[nd*2], seg[nd*2+1]);
    }
    int qry(){
        return -seg[1].second;
    }
} s;

struct segtree{
    ll seg[4*N];
    void build(int nd, int l, int r){
        if(l == r){
            seg[nd] = x[l - 1] % MOD;
            return;
        }
        int md = (l + r) >> 1;
        build(nd*2, l, md);
        build(nd*2+1, md+1, r);
        __int128 t = (__int128)seg[nd*2] * (__int128)seg[nd*2+1];
        seg[nd] = (ll)(t % MOD);
    }
    void upd(int nd, int l, int r, int pos, int v){
        if(l == r){
            seg[nd] = (v % MOD + MOD) % MOD;
            return;
        }
        int md = (l + r) >> 1;
        if(pos <= md) upd(nd*2, l, md, pos, v);
        else upd(nd*2+1, md+1, r, pos, v);
        __int128 t = (__int128)seg[nd*2] * (__int128)seg[nd*2+1];
        seg[nd] = (ll)(t % MOD);
    }
    ll qry(int nd, int l, int r, int ql, int qr){
        if(r < ql || l > qr) return 1;
        if(ql <= l && r <= qr) return seg[nd];
        int md = (l + r) >> 1;
        return ( (__int128)qry(nd*2, l, md, ql, qr) * (__int128)qry(nd*2+1, md+1, r, ql, qr)) % MOD;
    }
} pf;

int init(int NN, int X[], int Y[]){
    n = NN;
    for(int i = 0; i < n; ++i){
        x[i] = X[i];
        y[i] = Y[i];
    }
    vector<long double> arr(n+1, -INFINITY);
    long double pref = 0.0L;
    for(int k = 1; k <= n; ++k){
        pref += logl(x[k-1]);
        arr[k] = pref + logl(y[k-1]);
    }
    s.build_from_array(1, 1, n, arr);
    pf.build(1, 1, n);
    int idx = s.qry();
    ll prod = pf.qry(1, 1, n, 1, idx);
    ll ans = ( (__int128)prod * (__int128)(y[idx - 1] % MOD) ) % MOD;
    return (int)ans;
}

int updateX(int pos, int val){
    long double derm = logl(x[pos]);
    long double nw = logl((long double)val);
    long double dl = nw - derm;
    if(fabsl(dl) > 0.0L){
        s.upd(1, 1, n, pos + 1, n, dl);
    }
    x[pos] = val;
    pf.upd(1, 1, n, pos + 1, val);
    int idx = s.qry();
    ll prod = pf.qry(1, 1, n, 1, idx);
    ll ans = ( (__int128)prod * (__int128)(y[idx - 1] % MOD)) % MOD;
    return (int)ans;
}

int updateY(int pos, int val){
    long double derm = logl(y[pos]);
    long double nw = logl((long double)val);
    long double dl = nw - derm;
    if(fabsl(dl) > 0.0L){
        s.upd(1, 1, n, pos + 1, pos + 1, dl);
    }
    y[pos] = val;
    int idx = s.qry();
    ll prod = pf.qry(1, 1, n, 1, idx);
    ll ans = ((__int128)prod * (__int128)(y[idx - 1] % MOD)) % MOD;
    return (int)ans;
}

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