Submission #1243207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243207		BlockOG	Horses (IOI15_horses)	C++20	100 / 100	97 ms	29952 KiB

horses

#include <bits/stdc++.h>

// mrrrow meeow :3
// go play vivid/stasis now! it's free on steam

#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;

int ____init = [] {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

struct BigInt {
    int v;
    bool too_big;

    BigInt(int v) : v(v % 1000000007), too_big(v >= 1000000007) {}

    BigInt operator*(BigInt const &other) {
        BigInt res((long long)v * other.v % 1000000007);
        res.too_big = too_big ? true : v == 0 ? false : other.too_big ? true : other.v == 0 ? false : (long long)v * other.v >= 1000000007;
        return res;
    }

    bool operator>(BigInt const &other) {
        return too_big == other.too_big ? v > other.v : too_big > other.too_big;
    }
};

struct SegTree {
    BigInt xl, xr, y;

    SegTree() : xl(1), xr(1), y(0) {}

    SegTree combine(SegTree &r) {
        SegTree &l = *this;
        SegTree res;

        if (l.y > l.xr * r.xl * r.y) {
            res.xl = l.xl;
            res.xr = l.xr * r.xl * r.xr;
            res.y = l.y;
        } else {
            res.xl = l.xl * l.xr * r.xl;
            res.xr = r.xr;
            res.y = r.y;
        }

        return res;
    }
};

const int N = 1 << 19;
SegTree st[N * 2];

int init(int n, int x[], int y[]) {
    fo(i, 0, n) st[N + i].xl = BigInt(x[i]), st[N + i].y = BigInt(y[i]);
    of(i, 1, N) st[i] = st[i * 2].combine(st[i * 2 + 1]);
    return (st[1].xl * st[1].y).v;
}

int updateX(int pos, int val) {
    st[N + pos].xl = BigInt(val);
    for (int i = (N + pos) / 2; i > 0; i /= 2) st[i] = st[i * 2].combine(st[i * 2 + 1]);
    return (st[1].xl * st[1].y).v;
}

int updateY(int pos, int val) {
    st[N + pos].y = BigInt(val);
    for (int i = (N + pos) / 2; i > 0; i /= 2) st[i] = st[i * 2].combine(st[i * 2 + 1]);
    return (st[1].xl * st[1].y).v;
}

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