Submission #1275561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275561		domi	Horses (IOI15_horses)	C++20	Compilation error	0 ms	0 KiB

horses

#include <bits/stdc++.h>
// #include "horses.h"

// #define ll long long
// #define ld long ld
#define fi first
#define se second

#define sz(a) (ll)((a).size())
#define aint(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<ll>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using ld = long double;
using pii = std::pair<ll, ll>;

const ll NMAX = 2e5;
const ll MOD = 1e9 + 7;

using namespace std;

ld sp[NMAX + 5];
ll X[NMAX + 5], Y[NMAX + 5], n;


struct Seg {

    ll aint[4 * NMAX + 5];

    void build(ll nod = 1, ll st = 1, ll dr = n) {
        if (st == dr) {
            aint[nod] = X[st] % MOD;
            return;
        }

        ll m = (st + dr) >> 1;
        build(2 * nod, st, m);
        build(2 * nod + 1, m + 1, dr);
        aint[nod] = (aint[2 * nod] * aint[2 * nod + 1]) % MOD;
    }

    void update(ll pos, ll val, ll nod = 1, ll st = 1, ll dr = n) {
        if (st == dr) {
            aint[nod] = val % MOD;
            return;
        }

        ll m = (st + dr) >> 1;
        if (pos <= m)
            update(pos, val, 2 * nod, st, m);
        else
            update(pos, val, 2 * nod + 1, m + 1, dr);
        aint[nod] = (aint[2 * nod] * aint[2 * nod + 1]) % MOD;
    }

    ll query(ll l, ll r, ll nod = 1, ll st = 1, ll dr = n) {
        if (st > r || dr < l) return 1;
        if (l <= st && dr <= r) return aint[nod];

        ll m = (st + dr) >> 1;
        return (query(l, r, 2 * nod, st, m) * query(l, r, 2 * nod + 1, m + 1, dr)) % MOD;
    }

}aint_prod;

struct Lazy_Seg {

    struct Node {
        ld val;
        ll p;

        Node() : val(numeric_limits<ld>::lowest()), p(0) {}

        static Node merge(const Node& left, const Node& right) {
            Node aux;
            aux.val = max(left.val, right.val);
            aux.p = (left.val > right.val ? left.p : right.p);
            return aux;
        }

    };

    Node aint[4 * NMAX + 5];
    ld lazy[4 * NMAX + 5];

    void build(ll nod = 1, ll st = 1, ll dr = n) {
        if (st == dr) {
            aint[nod].val = sp[st] + 1.0 * log(Y[st]);
            aint[nod].p = st;
            return;
        }

        ll m = (st + dr) >> 1;
        build(2 * nod, st, m);
        build(2 * nod + 1, m + 1, dr);
        aint[nod] = Node::merge(aint[2 * nod], aint[2 * nod + 1]);
    }

    void push(ll nod, ll st, ll dr) {
        if (lazy[nod] != 0) {
            aint[nod].val += lazy[nod];
            if (st != dr) {
                lazy[2 * nod] += lazy[nod];
                lazy[2 * nod + 1] += lazy[nod];
            }
            lazy[nod] = 0;
        }
    }

    void update(ll pos, ld v, ll nod = 1, ll st = 1, ll dr = n) {
        push(nod, st, dr);

        if (st == dr) {
            aint[nod].val += v;
            return;
        }

        ll m = (st + dr) >> 1;
        if (pos <= m)
            update(pos, v, 2 * nod, st, m);
        else
            update(pos, v, 2 * nod + 1, m + 1, dr);
        aint[nod] = Node::merge(aint[2 * nod], aint[2 * nod + 1]);
    }

    void range_add(ll l, ll r, ld v, ll nod = 1, ll st = 1, ll dr = n) {
        push(nod, st, dr);

        if (st > r || dr < l) return;
        if (l <= st && dr <= r) {
            lazy[nod] += v;
            push(nod, st, dr);
            return;
        }

        ll m = (st + dr) >> 1;
        range_add(l, r, v, 2 * nod, st, m);
        range_add(l, r, v, 2 * nod + 1, m + 1, dr);
        aint[nod] = Node::merge(aint[2 * nod], aint[2 * nod + 1]);
    }

    Node query(ll l, ll r, ll nod = 1, ll st = 1, ll dr = n) {
        push(nod, st, dr);

        if (st > r || dr < l) return Node();
        if (l <= st && dr <= r) return aint[nod];

        ll m = (st + dr) >> 1;
        return Node::merge(query(l, r, 2 * nod, st, m), query(l, r, 2 * nod + 1, m + 1, dr));
    }

}aint;

ll init(ll n_, ll a[], ll b[]) {
    n = n_;
    copy(a + 1, a + n + 1, X + 1);
    copy(b + 1, b + n + 1, Y + 1);

    for (ll i = 1; i <= n; ++i)
        sp[i] = sp[i - 1] + 1.0 * log(X[i]);
    aint.build();
    aint_prod.build();

    int p = aint.query(1, n).p;
    return Y[p] * aint_prod.query(1, p);
}

ll updateX(ll pos, ll val) {
    ld dif = 1.0 * log(val) - 1.0 * log(X[pos]);
    X[pos] = val;
    aint.range_add(pos, n, dif);
    aint_prod.update(pos, X[pos]);

    int p = aint.query(1, n).p;
    return Y[p] * aint_prod.query(1, p);
}

ll updateY(ll pos, ll val) {
    ld dif = 1.0 * log(val) - 1.0 * log(Y[pos]);
    Y[pos] = val;
    aint.update(pos, dif);

    int p = aint.query(1, n).p;
    return Y[p] * aint_prod.query(1, p);
}


// signed main() {
//     cin.tie(nullptr)->sync_with_stdio(false);
//
//     ll N; cin >> N;
//     vector<ll> a(N+1), b(N+1);
//     for (ll i = 1; i <= N; ++i) cin >> a[i];
//     for (ll i = 1; i <= N; ++i) cin >> b[i];
//     ll M; cin >> M;
//     cout << init(N, a.data(), b.data()) << "\n";
//     while (M--) {
//         ll t, pos, val; cin >> t >> pos >> val;
//         if (t == 1) cout << updateX(pos, val) << "\n";
//         else cout << updateY(pos, val) << "\n";
//     }
//
//     return 0;
// } 

Compilation message (stderr)

/usr/bin/ld: /tmp/ccsqGogX.o: in function `main':
grader.c:(.text.startup+0xa1): undefined reference to `init(int, int*, int*)'
/usr/bin/ld: grader.c:(.text.startup+0xfb): undefined reference to `updateX(int, int)'
/usr/bin/ld: grader.c:(.text.startup+0x155): undefined reference to `updateY(int, int)'
collect2: error: ld returned 1 exit status