Submission #1281588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281588		nathlol2	Horses (IOI15_horses)	C++20	100 / 100	269 ms	122208 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;
ll f(ll a, ll b){
    return (a * b) % MOD;
}

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){
        seg[nd].first += lazy[nd];
        if (l != r) {
            lazy[nd * 2] += lazy[nd];
            lazy[nd * 2 + 1] += lazy[nd];
        }
        lazy[nd] = 0.0L;
    }
    void builda(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;
        builda(nd * 2, l, md, arr);
        builda(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);
        seg[nd] = f(seg[nd * 2], seg[nd * 2 + 1]);
    }

    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);
        seg[nd] = f(seg[nd * 2], seg[nd * 2 + 1]);
    }
    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 f(qry(nd * 2, l, md, ql, qr),qry(nd * 2 + 1, md + 1, r, ql, qr));
    }
} 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 pff = 0.0L;
    for(int k = 1;k<=n;k++){
        pff += logl(x[k - 1]);
        arr[k] = pff + logl(y[k - 1]);
    }
    s.builda(1, 1, n, arr);
    pf.build(1, 1, n);
    int idx = s.qry();
    ll prod = pf.qry(1, 1, n, 1, idx);
    ll ans = f(prod, y[idx - 1] % 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;
    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 = f(prod, y[idx - 1] % 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;
    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 = f(prod, y[idx - 1] % MOD);
    return (int)ans;
}

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