Submission #1275941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275941		domi	Horses (IOI15_horses)	C++20	17 / 100	146 ms	91768 KiB

horses

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

// #define int long long
// #define double long double
#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 = 5e5;
const ll MOD = 1e9 + 7;
const ll C = 1e8;

using namespace std;

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

inline ll modmul(ll a, ll b) {
    return (__int128)a * b % MOD;
}


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] = modmul(aint[2 * nod], aint[2 * nod + 1]);
    }

    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] = modmul(aint[2 * nod], aint[2 * nod + 1]);
    }

    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 modmul(query(l, r, 2 * nod, st, m), query(l, r, 2 * nod + 1, m + 1, dr));
    }

}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 = ((ll)(left.val * C) >= (ll)(right.val * C) ? 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 * log2l(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;

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

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

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

int32_t updateX(int32_t pos, int32_t val) {
    ld dif = 1.0 * log2l(val) - 1.0 * log2l(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 modmul(Y[p], aint_prod.query(1, p));
}

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

    int p = aint.query(1, n).p;
    return modmul(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;
// }

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