Submission #1199401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199401		matus192	Horses (IOI15_horses)	C++20	100 / 100	314 ms	121744 KiB

horses

#include "horses.h"

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;

#define REP(i, a, b) for (ll i = (a); i < (b); i++)
#define FOR(i, x) for (auto &i : x)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LMIN LONG_LONG_MIN
#define LMAX LONG_LONG_MAX
#define MOD 1000000007
#define SIR 1000000009

ll n;
vll X, Y;

ll power(ll a, ll e) {
    if (e == 0) return 1;
    ll res = power(a, e / 2);
    res = (res * res) % MOD;
    if (e % 2 == 1) {
        res = (res * a) % MOD;
    }

    return res;
}

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

struct Node {
    ll l, r;
    Node *lson, *rson;
    ll lazy, val;
    long double LAZY, VAL;

    Node(ll vl, ll vr, vector<pair<long double, ll>> &init) {
        l = vl;
        r = vr;
        lazy = 1;
        LAZY = 0;
        if (l + 1 == r) {
            lson = NULL;
            rson = NULL;
            val = init[l].ss;
            VAL = init[l].ff;
        } else {
            lson = new Node(vl, (vl + vr) / 2, init);
            rson = new Node((vl + vr) / 2, vr, init);
            if (lson->VAL > rson->VAL) {
                VAL = lson->VAL;
                val = lson->val;
            } else {
                VAL = rson->VAL;
                val = rson->val;
            }
        }
    }

    void remove_lazy() {
        if (l + 1 != r) {
            lson->lazy = (lson->lazy * lazy) % MOD;
            rson->lazy = (rson->lazy * lazy) % MOD;
            lson->val = (lson->val * lazy) % MOD;
            rson->val = (rson->val * lazy) % MOD;

            lson->LAZY = (lson->LAZY + LAZY);
            rson->LAZY = (rson->LAZY + LAZY);
            lson->VAL = (lson->VAL + LAZY);
            rson->VAL = (rson->VAL + LAZY);
        }
        lazy = 1;
        LAZY = 0;
    }

    void update(ll ql, ll qr, ll inc, long double INC) {
        if (qr <= l || ql >= r) return;
        if (ql <= l && qr >= r) {
            lazy = (lazy * inc) % MOD;
            val = (val * inc) % MOD;
            LAZY = (LAZY + INC);
            VAL = (VAL + INC);
            return;
        }
        remove_lazy();
        lson->update(ql, qr, inc, INC);
        rson->update(ql, qr, inc, INC);

        if (lson->VAL > rson->VAL) {
            VAL = lson->VAL;
            val = lson->val;
        } else {
            VAL = rson->VAL;
            val = rson->val;
        }
        return;
    }

    pair<long double, ll> find(ll ql, ll qr) {
        if (qr <= l || ql >= r) return {IMIN, LMIN};
        if (ql <= l && qr >= r) return {VAL, val};
        remove_lazy();
        auto lans = lson->find(ql, qr);
        auto rans = rson->find(ql, qr);

        if (lans.ff > rans.ff) {
            return lans;
        } else {
            return rans;
        }
    }
};

Node *root;

int init(int sz, int zmena[], int cena[]) {
    n = sz;
    REP(i,0,n) X.pb(zmena[i]);
    REP(i,0,n) Y.pb(cena[i]);
    ll akt = 1;
    long double AKT = 0;
    vector<pair<long double, ll>> init(n);
    REP(i, 0, n) {
        long double zmn = X[i], cna = Y[i];
        akt = (akt * X[i]) % MOD;
        AKT += log(zmn);
        ll cn = (akt * Y[i]) % MOD;
        long double CN = AKT + log(cna);
        init[i] = {CN, cn};
    }

    root = new Node(0, n, init);

    return root->find(0, root->r).ss;
}

int updateX(int x, int nw) {
    long double zmn = X[x];
    ll in = inv(X[x]);
    long double IN = -log(zmn);
    root->update(x, root->r, in, IN);

    X[x] = nw;

    long double NW = nw;
    NW = log(NW);
    root->update(x, root->r, nw, NW);
    return root->find(0, root->r).ss;
}

int updateY(int x, int nw) {
    long double cna = Y[x];
    ll in = inv(Y[x]);
    long double IN = -log(cna);
    root->update(x, x + 1, in, IN);

    Y[x] = nw;

    long double NW = nw;
    NW = log(NW);
    root->update(x, x + 1, nw, NW);
    return root->find(0, root->r).ss;
}

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