Submission #1308532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308532		purplelemon	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	0 / 100	390 ms	589824 KiB

timeleap

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

struct node {
    bool rng;
    int l, r;
    int x, st, out;
};

const int N = 3e5 + 10;
int n, q;
node tree1[4*N], tree2[4*N], ans, tmp;
pair<int,int> inps[N];

void upd(node &v,node &u1,node &u2) {
    if (u1.rng && u2.rng) {
        if (min(u1.r,u2.r) >= max(u1.l,u2.l)) {
            v.rng = 1;
            v.l = max(u1.l,u2.l);
            v.r = min(u1.r,u2.r);
        } else {
            v.rng = 0;
            if (u1.l > u2.r) {
                v.x = u1.l-u2.r;
                v.st = u1.l;
                v.out = u2.r;
            } else {
                v.x = 0;
                v.st = u1.r;
                v.out = u2.l;
            }
        }
    }
    if (u1.rng && !u2.rng) {
        v.rng = 0;
        v.out = u2.out;
        v.x = u2.x+max(0ll,u1.l-u2.st);
        v.st = max(u1.l,min(u1.r,u2.st));
    }
    if (!u1.rng && u2.rng) {
        v = u1;
        if (u1.out > u2.r) {
            v.out = u2.r;
            v.x += u1.out - u2.r;
        } else if (u1.out < u2.l) {
            v.out = u2.l;
        }
    }
    if (!u1.rng && !u2.rng) {
        v = u1;
        v.out = u2.out;
        v.x += u2.x+max(0ll,u1.out-u2.st);
    }
}

void build(int v,int tl,int tr) {
    if (tl == tr) {
        tree1[v].rng = 1;
        tree1[v].l = inps[tl].first-tl;
        tree1[v].r = inps[tl].second-tl-1;
        tree2[v].rng = 1;
        tree2[v].l = inps[tl].first-(n-tl);
        tree2[v].r = inps[tl].second-(n-tl)-1;
        return;
    }
    int mid = (tl+tr)/2;
    build(2*v,tl,mid);
    build(2*v+1,mid+1,tr);
    upd(tree1[v],tree1[2*v],tree1[2*v+1]);
    upd(tree2[v],tree2[2*v+1],tree2[2*v]);
}

void change(int v,int tl,int tr,int ind) {
    if (ind > tr || ind < tl) return;
    if (tl == tr) {
        tree1[v].rng = 1;
        tree1[v].l = inps[tl].first-tl;
        tree1[v].r = inps[tl].second-tl-1;
        tree2[v].rng = 1;
        tree2[v].l = inps[tl].first-(n-tl);
        tree2[v].r = inps[tl].second-(n-tl)-1;
        return;
    }
    int mid = (tl+tr)/2;
    change(2*v,tl,mid,ind);
    change(2*v+1,mid+1,tr,ind);
    upd(tree1[v],tree1[2*v],tree1[2*v+1]);
    upd(tree2[v],tree2[2*v+1],tree2[2*v]);
}

void GET(int v,int tl,int tr,int l,int r,int id) {
    if (r < l) return;
    if (tl == l && tr == r) {
        tmp = ans;
        if (id == 1) {
            upd(ans,tmp,tree1[v]);
        } else {
            upd(ans,tmp,tree2[v]);
        }
        return;
    }
    int mid = (tl+tr)/2;
    if (id == 1) {
        GET(2*v,tl,mid,l,min(r,mid),id);
        GET(2*v+1,mid+1,tr,max(l,mid+1),r,id);
    } else {
        GET(2*v+1,mid+1,tr,max(l,mid+1),r,id);
        GET(2*v,tl,mid,l,min(r,mid),id);
    }
}

/*
5 5
3 5
4 8
2 6
5 10
2 5 3 1 10
2 2 6 5 6
1 3 4 6
2 3 3 4 3
2 1 5 4 5
*/


void solve() {
    cin >> n >> q;
    for (int i = 1;i <= n-1;i++) {
        cin >> inps[i].first >> inps[i].second;
    }
    build(1,1,n-1);
    for (int i = 0;i < q;i++) {
        int t;
        cin >> t;
        if (t == 1) {
            int p, s, e;
            cin >> p >> s >> e;
            inps[p] = {s,e};
            change(1,1,n-1,p);
        } else {
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            if (a == c) {
                cout << max(0ll,b-d) << '\n';
                continue;
            }
            ans.rng = 1;
            ans.l = -1e18;
            ans.r = 1e18;
            if (a < c) {
                b -= a;
                d -= c;
                GET(1,1,n-1,a,c-1,1);
            } else {
                b -= (n-a+1);
                d -= (n-c+1);
                GET(1,1,n-1,c,a-1,2);
            }
            //cout << "a,b,c,d = " << a << ' ' << b << ' ' << c << ' ' << d << '\n';
            //cout << "ans.rng,l,r,x,st,out = " << ans.rng << ' ' << ans.l << ' ' << ans.r << ' ' << ans.x << ' ' << ans.st << ' ' << ans.out << '\n';
            int cost = 0, loc;
            if (ans.rng) {
                cost = max(0ll,b-ans.r);
                loc = b;
                if (loc < ans.l) loc = ans.l;
                if (loc > ans.r) loc = ans.r;
            } else {
                cost = ans.x+max(0ll,b-ans.st);
                loc = ans.out;
            }
            cout << cost + max(0ll,loc-d) << '\n';
        }
    }
}

/*
5 1
3 5
4 8
2 6
5 10
2 5 3 1 10
*/

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}

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