제출 #1308587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308587		purplelemon	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	100 / 100	385 ms	105576 KiB

timeleap

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

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

void upd(array<ll,6> &v,array<ll,6> &u1,array<ll,6> &u2) {
    if (u1[0] && u2[0]) {
        if (min(u1[2],u2[2]) >= max(u1[1],u2[1])) {
            v[0] = 1;
            v[1] = max(u1[1],u2[1]);
            v[2] = min(u1[2],u2[2]);
        } else {
            v[0] = 0;
            if (u1[1] > u2[2]) {
                v[3] = u1[1]-u2[2];
                v[4] = u1[1];
                v[5] = u2[2];
            } else {
                v[3] = 0;
                v[4] = u1[2];
                v[5] = u2[1];
            }
        }
    }
    if (u1[0] && !u2[0]) {
        v[0] = 0;
        v[5] = u2[5];
        v[3] = u2[3]+max(0ll,u1[1]-u2[4]);
        v[4] = max(u1[1],min(u1[2],u2[4]));
    }
    if (!u1[0] && u2[0]) {
        v = u1;
        if (u1[5] > u2[2]) {
            v[5] = u2[2];
            v[3] += u1[5] - u2[2];
        } else if (u1[5] < u2[1]) {
            v[5] = u2[1];
        }
    }
    if (!u1[0] && !u2[0]) {
        v = u1;
        v[5] = u2[5];
        v[3] += u2[3]+max(0ll,u1[5]-u2[4]);
    }
}

void build(int v,int tl,int tr) {
    if (tl == tr) {
        tree1[v][0] = 1;
        tree1[v][1] = inps[tl].first-tl;
        tree1[v][2] = inps[tl].second-tl-1;
        tree2[v][0] = 1;
        tree2[v][1] = inps[tl].first-(n-tl);
        tree2[v][2] = 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][0] = 1;
        tree1[v][1] = inps[tl].first-tl;
        tree1[v][2] = inps[tl].second-tl-1;
        tree2[v][0] = 1;
        tree2[v][1] = inps[tl].first-(n-tl);
        tree2[v][2] = 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);
    }
}


void solve() {
    cin >> n >> q;
    for (int i = 1;i <= n-1;i++) {
        cin >> inps[i].first >> inps[i].second;
    }
    if (n == 1) {
        for (int i = 0;i < q;i++) {
            int t, a, b, c, d;
            cin >> t >> a >> b >> c >> d;
            cout << max(0ll,(ll)b-d) << '\n';
        }
        return;
    }
    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(0,b-d) << '\n';
                continue;
            }
            ans[0] = 1;
            ans[1] = -21e8;
            ans[2] = 21e8;
            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);
            }
            ll cost = 0, loc;
            if (ans[0]) {
                cost = max(0ll,b-ans[2]);
                loc = b;
                if (loc < ans[1]) loc = ans[1];
                if (loc > ans[2]) loc = ans[2];
            } else {
                cost = ans[3]+max(0ll,b-ans[4]);
                loc = ans[5];
            }
            cout << cost + max(0ll,loc-d) << '\n';
        }
    }
}

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

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