Submission #922119

#	Time	Username	Problem	Language	Result	Execution time	Memory
922119		406	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	100 / 100	685 ms	105380 KiB

timeleap

    //besmellah
    //mage mikhad chi beshe?
    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i, a, b) for (int i = (a); i < (b); ++i) 
    #define int long long
    const int64_t INF = 1ll << 60;
    const int N = 3e5 + 50;
    int n, q, A[N], B[N], C[N], D[N], P[N], t[N], L[N], R[N], query_ans[N];
     
    struct node {
            int mxl, mnr, fil, fir, ansl, ansr, locl, locr;
    };
    int dist(int l, int r) {
            return max(r - l, 0ll);
    }
    void calc(node x, int l, int &rel, int &reans) {
            if (x.mxl <= x.mnr) {
                    rel = min(max(l, x.mxl), x.mnr);
                    reans += dist(rel, l);
            }
            else {
                    int dl = dist(x.fil, l) + x.ansl;
                    int dr = dist(x.fir, l) + x.ansr;
                    if (dl < dr) {
                            reans += dl;
                            rel = x.locl;
                    }
                    else {
                            reans += dr; 
                            rel = x.locr;
                    }
            }
    }
     
    node operator +(node l, node r) {
            node R;
            R.mxl = max(l.mxl, r.mxl);
            R.mnr = min(l.mnr, r.mnr);
            if (R.mxl <= R.mnr) {
                    R.ansl = R.ansr = 0;
                    R.locl = R.mxl;
                    R.locr = R.mnr;
                    R.fil = R.mxl;
                    R.fir = R.mnr;
                    return R;
            }
            R.fil = max(l.fil, r.fil);
            R.fir = min(l.fir, r.fir);
            if (l.mxl > l.mnr || R.fil > R.fir) {
                    R.fil = l.fil;
                    R.fir = l.fir;
            }
            R.ansl = R.ansr = 0;
            int tl, tr;
            calc(l, R.fil, tl, R.ansl);
            calc(r, tl, R.locl, R.ansl);
     
            calc(l, R.fir, tr, R.ansr);
            calc(r, tr, R.locr, R.ansr);
            return R;
    }
    node seg[N << 2];
     
    //int mxl, mnr, fil, fir, ansl, ansr, locl, locr;
    void build(int v, int l, int r) {
            if (l + 1 == r) {
                    seg[v] = {L[l], R[l], L[l], R[l], 0, 0, L[l], R[l]};
                    return;
            }
            int m = l + r >> 1;
            build(v << 1, l, m);
            build(v << 1 | 1, m, r);
            seg[v] = seg[v << 1] + seg[v << 1 | 1];
    }
    void update(int v, int l, int r, int ind, int L, int R) {
            if (l + 1 == r) {
                    seg[v] = {L, R, L, R, 0, 0, L, R};
                    return;
            }
            int m = l + r >> 1;
            if (ind < m)
                    update(v << 1, l, m, ind, L, R);
            else
                    update(v << 1 | 1, m, r, ind, L, R);
            seg[v] = seg[v << 1] + seg[v << 1 | 1];
    }
    //void calc(node x, int l, int &rel, int &reans) {
    void get(int v, int l, int r, int L, int R, int &time, int &re) {
            if (L <= l && r <= R) {
                    calc(seg[v], time, time, re);
                    return;
            }
            int m = l + r >> 1;
            if (R <= m)
                    get(v << 1, l, m, L, R, time, re);
            else if (L >= m)
                    get(v << 1 | 1, m, r, L, R, time, re);
            else {
                    get(v << 1, l, m, L, R, time, re);
                    get(v << 1 | 1, m, r, L, R, time, re);
            }
    }
     
    void solve() {
            FOR(i, 1, n) {
                    L[i] -= i;
                    R[i] -= i + 1;
            }
            build(1, 1, n);
            FOR(i, 0, q) {
                    B[i] -= (t[i] == 1 ? P[i] : A[i]);
                    D[i] -= (t[i] == 1 ? P[i] + 1 : C[i]);
                    if (t[i] == 1) {
                           update(1, 1, n, P[i], B[i], D[i]); 
                    }
                    else if (C[i] > A[i]) {
                            int time = B[i];
                            get(1, 1, n, A[i], C[i], time, query_ans[i]);
                            query_ans[i] += dist(D[i], time);
                    }
                    else if (C[i] == A[i])
                            query_ans[i] = dist(D[i], B[i]);
            }
            FOR(i, 1, n) {
                    L[i] += i;
                    R[i] += i + 1;
            }
            FOR(i, 0, q) {
                    B[i] += (t[i] == 1 ? P[i] : A[i]);
                    D[i] += (t[i] == 1 ? P[i] + 1 : C[i]);
            }
    }
     
    signed main() {
            ios::sync_with_stdio(0), cin.tie(0);
            cin >> n >> q;
            if (n == 1) {
                    while (q--) {
                            int t, a, b, c, d;
                            cin >> t >> a >> b >> c >> d;
                            cout << dist(d, b) << '\n';
                    }
                    return 0;
            }
            FOR(i, 1, n)
                    cin >> L[i] >> R[i];
            FOR(i, 0, q) {
                    cin >> t[i];
                    if (t[i] == 1) {
                            cin >> P[i] >> B[i] >> D[i];
                    }
                    else {
                            cin >> A[i] >> B[i] >> C[i] >> D[i];
                    }
            }
            solve();
            reverse(L + 1, L + n);
            reverse(R + 1, R + n);
            
            FOR(i, 0, q) {
                    if (t[i] == 1) {
                            P[i] = n - P[i];
                    }
                    else {
                            A[i] = n + 1 - A[i];
                            C[i] = n + 1 - C[i];
                    }
            }
            solve();
     
            FOR(i, 0, q)
                    if (t[i] == 2) {
                            cout << query_ans[i] << '\n';
                    }
     
            return 0;
    }
    //19:33:34

Compilation message (stderr)

timeleap.cpp: In function 'void build(long long int, long long int, long long int)':
timeleap.cpp:71:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |             int m = l + r >> 1;
      |                     ~~^~~
timeleap.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, long long int)':
timeleap.cpp:81:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |             int m = l + r >> 1;
      |                     ~~^~~
timeleap.cpp: In function 'void get(long long int, long long int, long long int, long long int, long long int, long long int&, long long int&)':
timeleap.cpp:94:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |             int m = l + r >> 1;
      |                     ~~^~~

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