Submission #871807

#	Time	Username	Problem	Language	Result	Execution time	Memory
871807		vjudge1	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	100 / 100	742 ms	121684 KiB

timeleap

#include <bits/stdc++.h>
using namespace std;

const int64_t inf = 1e11;

class state_t {
       public:
        bool fucked;
        int64_t dick, cock, penis, gay;
        state_t(int64_t dick = -inf, int64_t cock = +inf) : fucked(0), dick(dick), cock(cock), gay(0) {}

        int64_t shit(int64_t& nigga) const {
                int64_t res = 0;
                if (!fucked) {
                        if (nigga > cock) {
                                res = nigga - cock;
                                nigga = cock;
                        } else {
                                res = 0;
                                nigga = max(nigga, dick);
                        }
                } else {
                        res = max<int64_t>(0, nigga - cock) + gay;
                        nigga = penis;
                }
                return res;
        }

        state_t operator+(const state_t& other) const {
                state_t res;
                if (!fucked && !other.fucked) {
                        if (dick > other.cock) {
                                res.fucked = 1;
                                res.dick = res.cock = res.penis = dick;
                                res.gay = other.shit(res.penis);
                        } else if (cock < other.dick) {
                                res.fucked = 1;
                                res.dick = res.cock = res.penis = cock;
                                res.gay = other.shit(res.penis);
                        } else {
                                res = state_t(max(dick, other.dick), min(cock, other.cock));
                        }
                } else if (fucked) {
                        res = *this;
                        res.gay += other.shit(res.penis);
                } else if (other.fucked) {
                        res = other;
                        if (dick > other.cock) {
                                res.dick = res.cock = res.penis = dick;
                                res.gay = other.shit(res.penis);
                        } else if (cock < other.dick) {
                                res.cock = res.dick = res.penis = cock;
                                res.gay = other.shit(res.penis);
                        }
                }
                return res;
        }
};

class segtree_t {
       public:
        segtree_t *left, *right;
        int l, r, m;
        state_t vagina;

        segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1) {
                if (l == r) return;
                left = new segtree_t(l, m);
                right = new segtree_t(m + 1, r);
        }

        void Update(int i, const state_t& x) {
                if (l == r) {
                        vagina = x;
                        return;
                }
                if (i <= m) {
                        left->Update(i, x);
                } else {
                        right->Update(i, x);
                }
                vagina = left->vagina + right->vagina;
        }

        int64_t Get(int s, int t, int64_t& pussy) {
                if (l > t || r < s) return 0;
                if (s <= l && r <= t) {
                        int64_t res = vagina.shit(pussy);
                        return res;
                }
                int64_t res = 0;
                res += left->Get(s, t, pussy);
                res += right->Get(s, t, pussy);
                return res;
        }
};

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int n, q;
        cin >> n >> q;
        vector<int> l(n - 1), r(n - 1);
        vector<int> la(n - 1), ra(n - 1);
        vector<int> lb(n - 1), rb(n - 1);
        for (int i = 0; i < n - 1; i++) cin >> l[i] >> r[i], r[i]--;
        for (int i = 0; i < n - 1; i++) la[i] = l[i] - i, ra[i] = r[i] - i;
        for (int i = 0; i < n - 1; i++) lb[i] = l[i] + i, rb[i] = r[i] + i;

        segtree_t* treeL = new segtree_t(0, n);
        segtree_t* treeR = new segtree_t(0, n);

        for (int i = 0; i < n - 1; i++) {
                treeL->Update(i, state_t(la[i], ra[i]));
                treeR->Update(n - i, state_t(lb[i], rb[i]));
        }

        while (q--) {
                int _;
                cin >> _;
                if (_ == 1) {
                        int i;
                        cin >> i;
                        i--;
                        int s, t;
                        cin >> s >> t;
                        t--;
                        treeL->Update(i, state_t(s - i, t - i));
                        treeR->Update(n - i, state_t(s + i, t + i));
                } else {
                        int64_t a, b, c, d;
                        cin >> a >> b >> c >> d;
                        a--, c--;
                        if (a == c) {
                                cout << max<int64_t>(0, b - d) << '\n';
                        } else if (a < c) {
                                b -= a, d -= c;
                                int64_t res = treeL->Get(a, c - 1, b);
                                cout << res + max<int64_t>(0, b - d) << '\n';
                        } else {
                                b += a - 1, d += c - 1;
                                a = n - a, c = n - c;
                                int64_t res = treeR->Get(a + 1, c, b);
                                cout << res + max<int64_t>(0, b - d) << '\n';
                        }
                }
        }
}

Compilation message (stderr)

timeleap.cpp: In constructor 'segtree_t::segtree_t(int, int)':
timeleap.cpp:66:51: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |         segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1) {
      |                                                 ~~^~~

• Subtask 1: 4 / 4
• Subtask 2: 30 / 30
• Subtask 3: 66 / 66