Submission #1198668

#TimeUsernameProblemLanguageResultExecution timeMemory
1198668matus192Horses (IOI15_horses)C++20
Compilation error
0 ms0 KiB
#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 zmena, cena;

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;
        }
    }
};

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

    Node root(0, n, init);

    cout << root.find(0, n).ss << '\n';

    ll q;
    cin >> q;
    REP(i, 0, q) {
        ll t;
        cin >> t;
        ll x, nw;
        cin >> x >> nw;
        if (t == 1) {
            long double zmn = zmena[x];
            ll in = inv(zmena[x]);
            long double IN = -log(zmn);
            root.update(x, n+50, in, IN);

            zmena[x] = nw;

            long double NW = nw;
            NW = log(NW);
            root.update(x, n+50, nw, NW);

        } else {
            long double cna = cena[x];
            ll in = inv(cena[x]);
            long double IN = -log(cna);
            root.update(x, x+1, in, IN);

            cena[x] = nw;

            long double NW = nw;
            NW = log(NW);
            root.update(x, x+1, nw, NW);
        }
        cout << root.find(0, n).ss << '\n';
    }

    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccBqoMzL.o: in function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'; /tmp/cc61VSY6.o:horses.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccBqoMzL.o: in function `main':
grader.c:(.text.startup+0xb1): undefined reference to `init(int, int*, int*)'
/usr/bin/ld: grader.c:(.text.startup+0x10b): undefined reference to `updateX(int, int)'
/usr/bin/ld: grader.c:(.text.startup+0x165): undefined reference to `updateY(int, int)'
collect2: error: ld returned 1 exit status