Submission #1000686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000686		ProtonDecay314	Horses (IOI15_horses)	C++17	100 / 100	905 ms	136656 KiB

horses

/*
IOI 2015: Horses
(AC)

Learnings:
1. Combine after recursing in a segtree
2. Don't forget to combine after recursing in a segtree
3. Don't forget to combine after recursing in a segtree

Proof of correctness:
Suppose that X[i + 1]X[i + 2]...X[j]Y[j] > Y[i]

Thus, in this case, it makes sense to keep the horse in year i and sell it in year j

But the cost of selling a horse is independent of the number of horses you sell

Thus, if it makes sense to keep one horse, it makes sense to keep ALL horses since
every horse kept would yield the same return

Finally, notice that we can multiply both sides of the inequality above by X[0]X[1]...X[i]:

X[0]X[1]...X[i]X[i + 1]X[i + 2]...X[j]Y[j] > X[0]X[1]...X[i]Y[i]

Thus, it is indeed optimal to pick the year i with the largest X[0]X[1]...X[i]Y[i]
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;

const ll MOD = 1'000'000'007ll;
const ll INF = 1'000'000'008ll;
vll y_arr;

class TreeX {
    public:
        ll l, r, v, vmod;
        TreeX* lt;
        TreeX* rt;

        TreeX(ll a_l, ll a_r): l(a_l), r(a_r), v(1), vmod(1), lt(nullptr), rt(nullptr) {};

        static inline ll v_combine(ll a, ll b) {
            return min(a * b, INF);
        }

        static inline ll vmod_combine(ll a, ll b) {
            return (a * b) % MOD;
        }

        void combine() {
            v = TreeX::v_combine(lt->v, rt->v);
            vmod = TreeX::vmod_combine(lt->vmod, rt->vmod);
        }

        void build(const vll& a_v) {
            if(l == r) {
                v = vmod = a_v[l];
                return;
            }

            ll m = (l + r) >> 1;

            lt = new TreeX(l, m);
            rt = new TreeX(m + 1, r);
            lt->build(a_v);
            rt->build(a_v);
            combine(); // ! You forgot to combine!!
        }

        void upd(ll i, ll nv) {
            if(l == r && r == i) {
                v = vmod = nv;
                return;
            }
            ll m = (l + r) >> 1;
            if(i <= m) lt->upd(i, nv);
            else rt->upd(i, nv);
            combine(); // ! BRO YOU FORGOT TO COMBINE AGAIN
        }

        ll query_v(ll ql, ll qr) {
            if(ql > r || qr < l) return 1ll;
            if(ql == l && qr == r) return v;

            ll m = (l + r) >> 1;

            return TreeX::v_combine(lt->query_v(ql, min(m, qr)), rt->query_v(max(m + 1, ql), qr));
        }

        ll query_vmod(ll ql, ll qr) {
            if(ql > r || qr < l) return 1ll;
            if(ql == l && qr == r) return vmod;
            ll m = (l + r) >> 1;
            return TreeX::vmod_combine(lt->query_vmod(ql, min(m, qr)), rt->query_vmod(max(m + 1, ql), qr));
        }
};

TreeX* tx;

class TreeY {
    public:
        ll l, r, ind;
        TreeY* lt;
        TreeY* rt;

        TreeY(ll a_l, ll a_r): l(a_l), r(a_r), ind(0), lt(nullptr), rt(nullptr) {};

        void combine() {
            ll lv = y_arr[lt->ind];
            ll rv = TreeX::v_combine(tx->query_v(lt->ind + 1, rt->ind), y_arr[rt->ind]);

            if(lv > rv) ind = lt->ind;
            else ind = rt->ind;
        }

        void build() {
            if(l == r) {
                ind = l;
                return;
            }

            ll m = (l + r) >> 1;

            lt = new TreeY(l, m);
            rt = new TreeY(m + 1, r);
            lt->build();
            rt->build();

            combine();
        }

        void upd(ll i) {
            if(l == r && r == i) {
                ind = l;
                return;
            }

            ll m = (l + r) >> 1;
            if(i <= m) lt->upd(i);
            else rt->upd(i);
            combine();
        }
};

TreeY* ty;

ll cur_maxv() {
    // Rich people have hundreds of horses
    // I only have JUAN
    ll max_ind = ty->ind;
    return (tx->query_vmod(0, max_ind) * y_arr[max_ind]) % MOD;
}

ll ll_init(ll n, const vll& x, const vll& y) {
    y_arr = y; // Copy y array into new array

    tx = new TreeX(0, n - 1);
    tx->build(x);
    ty = new TreeY(0, n - 1);
    ty->build();

    return cur_maxv();
}

ll ll_updateX(ll pos, ll nv) {
    tx->upd(pos, nv);
    ty->upd(pos);
    return cur_maxv();
}

ll ll_updateY(ll pos, ll nv) {
    y_arr[pos] = nv;
    ty->upd(pos);
    return cur_maxv();
}

// IOI functions
int init(int N, int X[], int Y[]) {
    ll nll = N;
    vll x(N, 0);
    vll y(N, 0);

    for(ll i = 0; i < nll; i++) {
        x[i] = X[i];
        y[i] = Y[i];
    }

    return ll_init(nll, x, y);
}

int updateX(int pos, int val) {
    return ll_updateX(pos, val);
}

int updateY(int pos, int val) {
    return ll_updateY(pos, val);
}

Compilation message (stderr)

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:189:19: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  189 |     return ll_init(nll, x, y);
      |            ~~~~~~~^~~~~~~~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:193:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  193 |     return ll_updateX(pos, val);
      |            ~~~~~~~~~~^~~~~~~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:197:22: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  197 |     return ll_updateY(pos, val);
      |            ~~~~~~~~~~^~~~~~~~~~

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