Submission #871701

#	Time	Username	Problem	Language	Result	Execution time	Memory
871701		vjudge1	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	4 / 100	3098 ms	13236 KiB

timeleap

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

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;

        while (q--) {
                int _;
                cin >> _;
                if (_ == 1) {
                        int i;
                        cin >> i;
                        i--;
                        int s, t;
                        cin >> s >> t;
                        t--;
                        la[i] = s - i, ra[i] = t - i;
                        lb[i] = s + i, rb[i] = t + i;
                } else {
                        int a, b, c, d;
                        cin >> a >> b >> c >> d;
                        a--, c--;
                        auto& L = a <= c ? la : lb;
                        auto& R = a <= c ? ra : rb;

                        int64_t res = 0;

                        if (a <= c) {
                                b -= a, d -= c;
                                for (int i = a; i < c; i++) {
                                        b = max(b, L[i]);
                                        res += max(0, b - R[i]);
                                        b = min(b, R[i]);
                                }
                                b = max(b, d);
                                res += max(0, b - d);
                        } else {
                                b += a - 1, d += c - 1;
                                for (int i = a - 1; i >= c; i--) {
                                        b = max(b, L[i]);
                                        res += max(0, b - R[i]);
                                        b = min(b, R[i]);
                                }
                                b = max(b, d);
                                res += max(0, b - d);
                        }

                        cout << res << '\n';
                }
        }
}

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