Submission #1245831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245831		79brue	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	0 / 100	355 ms	589824 KiB

timeleap

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 1e18;

void input();
void solve();

int main(){
    input();
    solve();
}

struct segTree{
    struct Node{
        ll minLoc, maxLoc;
        ll distX, base;

        Node(){}
        Node(ll L, ll R){
            minLoc = L, maxLoc = R;
            distX = R, base = 0;
        }

        inline ll putLoc(ll x)const{
            return max(minLoc, min(maxLoc, x));
        }

        inline ll putDist(ll x)const{
            return base + max(0LL, x - distX);
        }

        Node operator+(const Node r)const{
            Node ret;
            ret.minLoc = r.putLoc(minLoc);
            ret.maxLoc = r.putLoc(maxLoc);
            ret.base = base + r.putDist(minLoc);
            ret.distX = ret.base - (r.putDist(maxLoc) + putDist(INF) - INF);
            return ret;
        }
    } tree[1<<20];

    void init(int i, int l, int r, ll *L, ll *R){
        if(l == r){
            tree[i] = Node(L[l] - l, R[l] - l);
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, L, R);
        init(i*2+1, m+1, r, L, R);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    void update(int i, int l, int r, int x, ll L, ll R){
        if(l == r){
            tree[i] = Node(L - l, R - l);
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, L, R);
        else update(i*2+1, m+1, r, x, L, R);
        tree[i] = tree[i*2] + tree[i*2+1];
    }

    Node query(int i, int l, int r, int s, int e){
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        if(e<=m) return query(i*2, l, m, s, e);
        else if(m<s) return query(i*2+1, m+1, r, s, e);
        else return query(i*2, l, m, s, e) + query(i*2+1, m+1, r, s, e);
    }
} segFwd, segRev;

int n, q;
ll L[300002], R[300002];
ll Lrev[300002], Rrev[300002];

void input(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<n; i++){
        scanf("%lld %lld", &L[i], &R[i]), R[i]--;
        Lrev[n-i] = L[i], Rrev[n-i] = R[i];
    }

    segFwd.init(1, 1, n-1, L, R);
    segRev.init(1, 1, n-1, Lrev, Rrev);
}

void solve(){
    while(q--){
        int qt;
        scanf("%d", &qt);
        if(qt == 1){
            int p; ll s, e;
            scanf("%d %lld %lld", &p, &s, &e);
            e--;

            segFwd.update(1, 1, n-1, p, s, e);
            segRev.update(1, 1, n-1, n-p, s, e);
        }
        else{
            int x1, x2; ll t1, t2;
            scanf("%d %lld %d %lld", &x1, &t1, &x2, &t2);

            if(x1 == x2){
                printf("%lld\n", t1 <= t2 ? 0 : t1 - t2);
                continue;
            }

            if(x1 < x2){
                t1 -= x1, t2 -= x2;
                segTree::Node tmp = segFwd.query(1, 1, n-1, x1, x2-1);
                ll ans = tmp.putDist(t1) + max(0LL, tmp.putLoc(t1) - t2);
                printf("%lld\n", ans);
            }
            else{
                x1 = n + 1 - x1, x2 = n + 1 - x2;
                t1 -= x1, t2 -= x2;
                segTree::Node tmp = segRev.query(1, 1, n-1, x1, x2-1);
                ll ans = tmp.putDist(t1) + max(0LL, tmp.putLoc(t1) - t2);
                printf("%lld\n", ans);
            }
        }
    }
}

Compilation message (stderr)

timeleap.cpp: In function 'void input()':
timeleap.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
timeleap.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         scanf("%lld %lld", &L[i], &R[i]), R[i]--;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp: In function 'void solve()':
timeleap.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         scanf("%d", &qt);
      |         ~~~~~^~~~~~~~~~~
timeleap.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |             scanf("%d %lld %lld", &p, &s, &e);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:105:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |             scanf("%d %lld %d %lld", &x1, &t1, &x2, &t2);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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