Submission #499963

#	Time	Username	Problem	Language	Result	Execution time	Memory
499963		blue	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	4 / 100	3061 ms	4760 KiB

timeleap

#include <iostream>
#include <vector>
#include <cassert>
#include <cstdio>
using namespace std;

using ll = long long;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q;
    cin >> N >> Q;

    ll L[N], R[N];
    for(int i = 1; i <= N-1; i++) cin >> L[i] >> R[i];

    for(int j = 1; j <= Q; j++)
    {
        int T;
        cin >> T;

        if(T == 1)
        {
            ll P, S, E;
            cin >> P >> S >> E;

            L[P] = S;
            R[P] = E;
        }
        else
        {
            ll A, B, C, D;
            cin >> A >> B >> C >> D;

            ll ans = 0;

            if(A <= C)
            {
                ll x = B;
                int p = A;
                while(p != C)
                {
                    // cerr << "p = " << p << '\n';
                    if(L[p] <= x && x <= R[p]-1)
                    {
                        x++;
                        p++;
                    }
                    else if(x > R[p] - 1)
                    {
                        ans += x - (R[p] - 1);
                        x = R[p] - 1;
                    }
                    else if(x < L[p])
                    {
                        x = L[p];
                    }
                }

                ans += max(0LL, x-D);
            }
            else
            {
                // cerr << "case 2\n";
                ll x = B;
                int p = A;
                // cerr << A << ' ' << C << '\n';
                while(p != C)
                {
                    // cerr << p << ' ' << x << '\n';
                    // cerr << "p = " << p << '\n';
                    if(L[p-1] <= x && x <= R[p-1]-1)
                    {
                        x++;
                        p--;
                    }
                    else if(x > R[p-1] - 1)
                    {
                        ans += x - (R[p-1] - 1);
                        x = R[p-1] - 1;
                    }
                    else if(x < L[p-1])
                    {
                        x = L[p-1];
                    }
                }

                ans += max(0LL, x-D);
            }

            cout << ans << '\n';
            // cout << ans << '\n';

            // if(j >= 1) assert(0);
        }
    }
}

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