Submission #1171061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171061		anteknne	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	4 / 100	3090 ms	4828 KiB

timeleap

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

const int MAXN = 1000 * 1000 + 181;

typedef long long ll;

ll p[MAXN];
ll k[MAXN];

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, q;
    cin >> n >> q;

    for (int i = 1; i < n; i ++) {
        cin >> p[i] >> k[i];

    }

    ll t, a, b, c, d;
    while (q --) {
        cin >> t;
        if (t == 1LL) {
            cin >> a >> b >> c;
            p[a] = b;
            k[a] = c;

        } else {
            cin >> a >> b >> c >> d;
            if (a < c) {
                ll wyn = 0;
                ll t = b;
                for (int i = a; i < c; i ++) {
                    if (p[i] <= t && t + 1 <= k[i]) {
                        t ++;
                        continue;
                    }
                    if (t < p[i]) {
                        t = p[i];
                    }
                    if (t + 1LL > k[i]) {
                        wyn += (t + 1LL - k[i]);
                        t = k[i] - 1;
                    }
                    t ++;
                }
                if (d < t) {
                    wyn += (t - d);
                }
                cout << wyn << "\n";
            } else {
                ll wyn = 0;
                ll t = b;
                for (int i = a - 1; i >= c; i --) {
                    if (p[i] <= t && t + 1 <= k[i]) {
                        t ++;
                        continue;
                    }
                    if (t < p[i]) {
                        t = p[i];
                    }
                    if (t + 1LL > k[i]) {
                        wyn += (t + 1LL - k[i]);
                        t = k[i] - 1;
                    }
                    t ++;
                }
                if (d < t) {
                    wyn += (t - d);
                }
                cout << wyn << "\n";
            }
        }
    }



    return 0;
}

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