oj.uz

Submission #484793

# Submission time Handle Problem Language Result Execution time Memory
484793 2021-11-05T13:32:11 Z jalsol Horses (IOI15_horses) C++17
100 / 100
 392 ms 156000 KB 
#include "horses.h"
#ifdef LOCAL
#include "local.h"
#else
#include <bits/stdc++.h>
#define debug(...)
#define DB(...)
#endif

using namespace std;

static const bool __initialization = []() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cout << setprecision(12) << fixed;
    return true;
}();

using ll = long long;
using ld = long double;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)
#define Fe(...) for (auto __VA_ARGS__)

template <class C> inline int isz(const C& c) { return static_cast<int>(c.size()); }
template <class T> inline bool chmin(T& a, const T& b) { return (a > b) ? a = b, true : false; }
template <class T> inline bool chmax(T& a, const T& b) { return (a < b) ? a = b, true : false; }

constexpr ld eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// =============================================================================

constexpr int maxn = 5e5 + 5;

// rewriting mint
struct mint {
    int v;
    static constexpr int mod = 1e9 + 7;

    mint() : v(0) {}
    mint(ll _v) : v(_v % mod) { v += mod * (v < 0); }

    friend mint power(mint a, ll b) {
        mint ret = 1;

        while (b) {
            if (b & 1) ret *= a;
            b >>= 1;
            a *= a;
        }

        return ret;
    }

    // TODO: add more operator
    mint& operator*=(const mint& o) {
        return *this = mint(1LL * v * o.v);
    }

    mint& operator/=(const mint& o) {
        return *this *= power(o, mod - 2);
    }

    friend mint operator*(const mint& a, const mint& b) {
        return mint(a) *= b;
    }

    friend mint operator/(const mint& a, const mint& b) {
        return mint(a) /= b;
    }

    friend bool operator==(const mint& a, const mint& b) {
        return a.v == b.v;
    }
};

void __print_single(const mint& a) {
    cerr << a.v;
}

int n;
int X[maxn];
int Y[maxn];
ld plog[maxn];
mint pprod[maxn];

namespace segtree {
struct Node {
    ld log;
    mint prod;

    Node() : log(0.0), prod(1) {}
    Node(ld x, const mint& y) : log(x), prod(y) {}

    bool operator<(const Node& o) const {
        return log < o.log;
    }

    Node& operator+=(const Node& o) {
        log += o.log;
        prod *= o.prod;
        return *this;
    }
};

void __print_single(const Node& a) {
    cerr << "{ " << a.log << ", " << a.prod.v << " }";
}

#define m ((l + r) / 2)
#define lc (2 * i + 1)
#define rc (2 * i + 2)

Node tree[maxn << 2];
Node lazy[maxn << 2];

void build(int i, int l, int r) {
    if (l == r) {
        tree[i] = {plog[l] + log(Y[l]), pprod[l] * Y[l]};
        return;
    }

    build(lc, l, m);
    build(rc, m + 1, r);
    tree[i] = max(tree[lc], tree[rc]);
}

void push(int i, int l, int r) {
    if (lazy[i].prod == 1) return;

    tree[i] += lazy[i];

    if (l < r) {
        lazy[lc] += lazy[i];
        lazy[rc] += lazy[i];
    }

    lazy[i] = Node();
}

void update(int i, int l, int r, int u, int v, const mint& mul, ld lg) {
    push(i, l, r);
    if (v < l || r < u) return;

    if (u <= l && r <= v) {
        lazy[i] = {lg, mul};
        push(i, l, r);
        return;
    }

    update(lc, l, m, u, v, mul, lg);
    update(rc, m + 1, r, u, v, mul, lg);
    tree[i] = max(tree[lc], tree[rc]);
}

#undef m
#undef lc
#undef rc
} // namespace segtree
using namespace segtree;

int init(int _N, int _X[], int _Y[]) {
    n = _N;
    mempcpy(X + 1, _X, n * sizeof(int));
    mempcpy(Y + 1, _Y, n * sizeof(int));

    plog[1] = log(X[1]);
    pprod[1] = X[1];

    For (i, 2, n) {
        plog[i] = plog[i - 1] + log(X[i]);
        pprod[i] = pprod[i - 1] * X[i];
    }

    build(0, 1, n);

    return tree[0].prod.v;
}

int updateX(int pos, int val) {
    ++pos;

    mint mul = mint(val) / mint(X[pos]);
    ld lg = -log(X[pos]) + log(val);
    X[pos] = val;

    update(0, 1, n, pos, n, mul, lg);

    return tree[0].prod.v;
}

int updateY(int pos, int val) {
    ++pos;

    mint mul = mint(val) / mint(Y[pos]);
    ld lg = -log(Y[pos]) + log(val);
    Y[pos] = val;

    update(0, 1, n, pos, pos, mul, lg);

    return tree[0].prod.v;
}

// selling everything at one single day I suppose?
// if there's an answer of selling at both days,
// then keeping instead of selling at the first day,
// keeping the number of horses grow then sell at the second day
// will profit more because of the property of exponential functions
// ig?
// but the values will get very, very large, very quickly...
// if it passes the first subtask, then the logic could be correct

// holy shit why did I forget logarithm...
// no wonder people solved this with ease

Compilation message

horses.cpp: In constructor 'mint::mint(ll)':
horses.cpp:48:24: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   48 |     mint(ll _v) : v(_v % mod) { v += mod * (v < 0); }
      |                     ~~~^~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 127428 KB Output is correct
2 Correct 75 ms 127536 KB Output is correct
3 Correct 69 ms 127428 KB Output is correct
4 Correct 70 ms 127592 KB Output is correct
5 Correct 73 ms 127428 KB Output is correct
6 Correct 73 ms 127484 KB Output is correct
7 Correct 73 ms 127416 KB Output is correct
8 Correct 69 ms 127412 KB Output is correct
9 Correct 75 ms 127428 KB Output is correct
10 Correct 72 ms 127412 KB Output is correct
11 Correct 72 ms 127428 KB Output is correct
12 Correct 75 ms 127436 KB Output is correct
13 Correct 79 ms 127428 KB Output is correct
14 Correct 74 ms 127456 KB Output is correct
15 Correct 74 ms 127556 KB Output is correct
16 Correct 72 ms 127428 KB Output is correct
17 Correct 70 ms 127576 KB Output is correct
18 Correct 74 ms 127516 KB Output is correct
19 Correct 74 ms 127464 KB Output is correct
20 Correct 75 ms 127504 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 127412 KB Output is correct
2 Correct 73 ms 127432 KB Output is correct
3 Correct 81 ms 127508 KB Output is correct
4 Correct 71 ms 127436 KB Output is correct
5 Correct 68 ms 127480 KB Output is correct
6 Correct 72 ms 127532 KB Output is correct
7 Correct 71 ms 127428 KB Output is correct
8 Correct 70 ms 127492 KB Output is correct
9 Correct 76 ms 127428 KB Output is correct
10 Correct 73 ms 127428 KB Output is correct
11 Correct 69 ms 127428 KB Output is correct
12 Correct 73 ms 127528 KB Output is correct
13 Correct 68 ms 127428 KB Output is correct
14 Correct 72 ms 127468 KB Output is correct
15 Correct 68 ms 127472 KB Output is correct
16 Correct 73 ms 127428 KB Output is correct
17 Correct 73 ms 127556 KB Output is correct
18 Correct 75 ms 127428 KB Output is correct
19 Correct 73 ms 127528 KB Output is correct
20 Correct 70 ms 127428 KB Output is correct
21 Correct 69 ms 127524 KB Output is correct
22 Correct 68 ms 127464 KB Output is correct
23 Correct 70 ms 127536 KB Output is correct
24 Correct 76 ms 127556 KB Output is correct
25 Correct 73 ms 127512 KB Output is correct
26 Correct 71 ms 127560 KB Output is correct
27 Correct 68 ms 127556 KB Output is correct
28 Correct 70 ms 127588 KB Output is correct
29 Correct 74 ms 127568 KB Output is correct
30 Correct 71 ms 127580 KB Output is correct
31 Correct 68 ms 127512 KB Output is correct
32 Correct 73 ms 127560 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 145548 KB Output is correct
2 Correct 376 ms 145676 KB Output is correct
3 Correct 338 ms 145540 KB Output is correct
4 Correct 354 ms 145604 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 127528 KB Output is correct
2 Correct 66 ms 127472 KB Output is correct
3 Correct 67 ms 127416 KB Output is correct
4 Correct 66 ms 127424 KB Output is correct
5 Correct 69 ms 127476 KB Output is correct
6 Correct 69 ms 127464 KB Output is correct
7 Correct 74 ms 127420 KB Output is correct
8 Correct 69 ms 127464 KB Output is correct
9 Correct 66 ms 127428 KB Output is correct
10 Correct 73 ms 127484 KB Output is correct
11 Correct 70 ms 127520 KB Output is correct
12 Correct 77 ms 127452 KB Output is correct
13 Correct 84 ms 127428 KB Output is correct
14 Correct 69 ms 127476 KB Output is correct
15 Correct 70 ms 127468 KB Output is correct
16 Correct 73 ms 127428 KB Output is correct
17 Correct 76 ms 127444 KB Output is correct
18 Correct 76 ms 127496 KB Output is correct
19 Correct 68 ms 127492 KB Output is correct
20 Correct 69 ms 127452 KB Output is correct
21 Correct 73 ms 127528 KB Output is correct
22 Correct 76 ms 127428 KB Output is correct
23 Correct 78 ms 127564 KB Output is correct
24 Correct 70 ms 127524 KB Output is correct
25 Correct 74 ms 127556 KB Output is correct
26 Correct 76 ms 127492 KB Output is correct
27 Correct 74 ms 127464 KB Output is correct
28 Correct 74 ms 127516 KB Output is correct
29 Correct 72 ms 127460 KB Output is correct
30 Correct 70 ms 127556 KB Output is correct
31 Correct 71 ms 127576 KB Output is correct
32 Correct 74 ms 127460 KB Output is correct
33 Correct 131 ms 144708 KB Output is correct
34 Correct 138 ms 144748 KB Output is correct
35 Correct 143 ms 144664 KB Output is correct
36 Correct 155 ms 144708 KB Output is correct
37 Correct 119 ms 144708 KB Output is correct
38 Correct 120 ms 144612 KB Output is correct
39 Correct 108 ms 144580 KB Output is correct
40 Correct 129 ms 144640 KB Output is correct
41 Correct 113 ms 144692 KB Output is correct
42 Correct 112 ms 144708 KB Output is correct
43 Correct 121 ms 144652 KB Output is correct
44 Correct 120 ms 149512 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 127520 KB Output is correct
2 Correct 76 ms 127524 KB Output is correct
3 Correct 72 ms 127488 KB Output is correct
4 Correct 70 ms 127548 KB Output is correct
5 Correct 69 ms 127508 KB Output is correct
6 Correct 73 ms 127508 KB Output is correct
7 Correct 76 ms 127428 KB Output is correct
8 Correct 68 ms 127500 KB Output is correct
9 Correct 69 ms 127428 KB Output is correct
10 Correct 74 ms 127428 KB Output is correct
11 Correct 73 ms 127508 KB Output is correct
12 Correct 73 ms 127476 KB Output is correct
13 Correct 67 ms 127436 KB Output is correct
14 Correct 68 ms 127500 KB Output is correct
15 Correct 68 ms 127428 KB Output is correct
16 Correct 73 ms 127496 KB Output is correct
17 Correct 73 ms 127472 KB Output is correct
18 Correct 68 ms 127488 KB Output is correct
19 Correct 69 ms 127424 KB Output is correct
20 Correct 71 ms 127524 KB Output is correct
21 Correct 75 ms 127456 KB Output is correct
22 Correct 82 ms 127428 KB Output is correct
23 Correct 73 ms 127592 KB Output is correct
24 Correct 71 ms 127512 KB Output is correct
25 Correct 77 ms 127556 KB Output is correct
26 Correct 73 ms 127484 KB Output is correct
27 Correct 72 ms 127556 KB Output is correct
28 Correct 66 ms 127576 KB Output is correct
29 Correct 72 ms 127556 KB Output is correct
30 Correct 74 ms 127468 KB Output is correct
31 Correct 74 ms 127628 KB Output is correct
32 Correct 67 ms 127476 KB Output is correct
33 Correct 201 ms 145604 KB Output is correct
34 Correct 371 ms 145604 KB Output is correct
35 Correct 347 ms 145384 KB Output is correct
36 Correct 381 ms 145348 KB Output is correct
37 Correct 125 ms 144268 KB Output is correct
38 Correct 147 ms 144280 KB Output is correct
39 Correct 140 ms 144232 KB Output is correct
40 Correct 141 ms 143880 KB Output is correct
41 Correct 112 ms 143872 KB Output is correct
42 Correct 117 ms 143904 KB Output is correct
43 Correct 107 ms 143744 KB Output is correct
44 Correct 126 ms 143628 KB Output is correct
45 Correct 103 ms 143668 KB Output is correct
46 Correct 112 ms 143752 KB Output is correct
47 Correct 115 ms 143360 KB Output is correct
48 Correct 116 ms 149484 KB Output is correct
49 Correct 346 ms 149248 KB Output is correct
50 Correct 313 ms 149188 KB Output is correct
51 Correct 392 ms 156000 KB Output is correct
52 Correct 229 ms 155460 KB Output is correct
53 Correct 284 ms 147628 KB Output is correct
54 Correct 218 ms 148084 KB Output is correct
55 Correct 205 ms 146252 KB Output is correct
56 Correct 248 ms 151108 KB Output is correct
57 Correct 178 ms 146912 KB Output is correct
58 Correct 197 ms 147396 KB Output is correct
59 Correct 123 ms 149460 KB Output is correct