Submission #1256061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256061		trandangquang	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	0 / 100	241 ms	55872 KiB

timeleap

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

struct Node {
    int x=0, y=0;
    ll p=-1;   // p == -1 => interval [x,y]; p >= 0 => path x->y with cost p
    bool valid=false;
};

int n, q;
const int MAXN = 300300;
int fl[MAXN], fr[MAXN];

// semigroup combine (keeps associativity)
Node combine(const Node &u, const Node &v){
    if(!u.valid) return v;
    if(!v.valid) return u;
    Node res; res.valid = true;
    if(u.p == -1 && v.p == -1){
        if(u.x > v.y){
            res.x = u.x; res.y = v.y; res.p = (ll)u.x - v.y;
        } else if(u.y < v.x){
            res.x = u.y; res.y = v.x; res.p = 0;
        } else {
            res.x = max(u.x, v.x);
            res.y = min(u.y, v.y);
            res.p = -1;
        }
    } else if(u.p == -1 && v.p != -1){
        res.x = min( max(u.x, v.x), u.y );
        res.y = v.y;
        res.p = v.p + max(0, u.x - v.x);
    } else if(u.p != -1 && v.p == -1){
        res.x = u.x;
        res.y = max( min(u.y, v.y), v.x );
        res.p = u.p + max(0, u.y - v.y);
    } else {
        res.x = u.x;
        res.y = v.y;
        res.p = u.p + v.p + max(0, u.y - v.x);
    }
    return res;
}

struct IterSeg {
    int mode;           // 1 = normal order, 2 = reversed children order
    int m;              // number of leaves (n-1)
    int base;           // power of two >= m
    vector<Node> seg;   // size 2*base

    void init(int _m, int _mode){
        m = _m;
        mode = _mode;
        base = 1;
        while(base < max(1, m)) base <<= 1;
        seg.assign(2*base, Node());
        // initially all invalid; we'll set actual leaves later
    }

    void set_leaf(int pos, const Node &val){ // pos: 1..m
        int i = base + (pos - 1);
        seg[i] = val;
        seg[i].valid = true;
        // update parents
        for(i >>= 1; i; i >>= 1){
            if(mode == 1) seg[i] = combine(seg[i<<1], seg[i<<1|1]);
            else seg[i] = combine(seg[i<<1|1], seg[i<<1]);
        }
    }

    // build leaves from arrays fl,fr (call after init and after fl/fr filled)
    void build_all(){
        for(int i = 1; i <= m; ++i){
            Node tmp;
            if(mode == 1){
                tmp.x = fl[i] - i;
                tmp.y = fr[i] - i - 1;
            } else {
                tmp.x = fl[i] - (n - i);
                tmp.y = fr[i] - (n - i) - 1;
            }
            tmp.p = -1; tmp.valid = true;
            seg[base + (i-1)] = tmp;
        }
        // other leaves remain invalid
        for(int i = base - 1; i >= 1; --i){
            if(mode == 1) seg[i] = combine(seg[i<<1], seg[i<<1|1]);
            else seg[i] = combine(seg[i<<1|1], seg[i<<1]);
        }
    }

    // iterative range query on [l..r] (1-based, inclusive). returns Node (may be invalid if l>r)
    Node query(int l, int r){
        Node leftAccum, rightAccum;
        int L = base + (l - 1), R = base + (r - 1);
        while(L <= R){
            if(L & 1){
                if(!leftAccum.valid) leftAccum = seg[L];
                else leftAccum = combine(leftAccum, seg[L]);
                ++L;
            }
            if(!(R & 1)){
                if(!rightAccum.valid) rightAccum = seg[R];
                else rightAccum = combine(seg[R], rightAccum);
                --R;
            }
            L >>= 1; R >>= 1;
        }
        if(!leftAccum.valid) return rightAccum;
        if(!rightAccum.valid) return leftAccum;
        return combine(leftAccum, rightAccum);
    }

    // point update: replace leaf pos with Node val (pos:1..m)
    void update(int pos, const Node &val){
        set_leaf(pos, val);
    }
};


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for(int i = 1; i <= n-1; ++i) cin >> fl[i] >> fr[i];

    IterSeg st1, st2;
    st1.init(n-1, 1);
    st2.init(n-1, 2);
    st1.build_all();
    st2.build_all();

    while(q--){
        int type; cin >> type;
        if(type == 1){
            int p, s, e; cin >> p >> s >> e;
            // update arrays if you want to keep them
            fl[p] = s; fr[p] = e;
            Node a; a.valid = true; a.p = -1;
            a.x = s - p; a.y = e - p - 1;
            st1.update(p, a);
            Node b; b.valid = true; b.p = -1;
            b.x = s - (n - p); b.y = e - (n - p) - 1;
            st2.update(p, b);
        } else {
            int a, b_time, c, d_time;
            cin >> a >> b_time >> c >> d_time;
            if(a == c){
                cout << max(0, b_time - d_time) << '\n';
                continue;
            }

            Node left, mid, right, total;
            if(a < c){
                // forward direction using st1, query [a, c-1]
                int b = b_time - a;
                int d = d_time - c;
                Node start; start.valid = true; start.p = -1; start.x = b; start.y = b;
                Node end; end.valid = true; end.p = -1; end.x = d; end.y = d;
                mid = st1.query(a, c-1);
                total = combine(combine(start, mid), end);
            } else {
                // backward direction using st2, query [c, a-1]
                // note the time normalization used in original implementation
                int b = b_time - (n - (a - 1));
                int d = d_time - (n - (c - 1));
                Node start; start.valid = true; start.p = -1; start.x = b; start.y = b;
                Node end; end.valid = true; end.p = -1; end.x = d; end.y = d;
                mid = st2.query(c, a-1);
                total = combine(combine(start, mid), end);
            }
            ll ans = (total.valid ? max(0ll, total.p) : 0ll);
            cout << ans << '\n';
        }
    }
    return 0;
}

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