oj.uz

Submission #537979

# Submission time Handle Problem Language Result Execution time Memory
537979 2022-03-16T01:41:28 Z czhang2718 Bitaro, who Leaps through Time (JOI19_timeleap) C++17
0 / 100
 3000 ms 524288 KB 
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;

struct P{
    int l, r;
    ll k;

    inline P(){}
    inline P(int l, int r, ll k): l(l), r(r), k(k) {}

    inline friend P operator + (P a, P b){
        if(a.k==-1 && b.k==-1){
            if(max(a.l, b.l)<=min(a.r, b.r)) return P(max(a.l, b.l), min(a.r, b.r), -1);
            if(a.l>b.r) return P(a.l, b.r, a.l-b.r);
            if(a.r<b.l) return P(a.r, b.l, 0);
        }
        if(a.k==-1){
            if(b.l>a.r) return P(a.r, b.r, b.k);
            if(b.l<a.l) return P(a.l, b.r, b.k+a.l-b.l);
            return b;
        }
        if(b.k==-1){
            if(b.l>a.r) return P(a.l, b.l, a.k);
            if(b.r<a.r) return P(a.l, b.r, a.k+a.r-b.r);
            return a;
        }
        return P(a.l, b.r, a.k+b.k+max(0, a.r-b.l));
    }
};

const int N=300000;
int n, q;

struct segtree{
    vector<P> seg;

    segtree(){
        seg.resize(4*n);
    }

    void build(vector<P> v, int x, int lx, int rx){
        if(rx-lx==1){
            seg[x]=v[lx];
            return;
        }
        int m=(lx+rx)/2;
        build(v, 2*x+1, lx, m);
        build(v, 2*x+2, m, rx);
        seg[x]=seg[2*x+1]+seg[2*x+2];
        // cout << "seg " << lx << " " << rx << " " << seg[x].l << " " << seg[x].r << " " << seg[x].k << "\n";
    }

    void build(vector<P> v){ build(v, 0, 0, n-1); }

    void upd(int i, P p, int x, int lx, int rx){
        if(rx-lx==1){
            seg[x]=p; 
            return;
        }
        int m=(lx+rx)/2;
        if(i<m) upd(i, p, 2*x+1, lx, m);
        else upd(i, p, 2*x+2, m, rx);
        seg[x]=seg[2*x+1]+seg[2*x+2];
    }

    void upd(int i, P p){ upd(i, p, 0, 0, n-1); }

    P query(int l, int r, int x, int lx, int rx){
        if(lx>=l && rx<=r) return seg[x];
        if(lx>=r || rx<=l) return P(-1e9, 1e9, -1);
        int m=(lx+rx)/2;
        return query(l, r, 2*x+1, lx, m)+query(l, r, 2*x+2, m, rx);
    }

    P query(int l, int r){ return query(l, r, 0, 0, n-1); }
};


int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> q;

    vector<P> path1, path2;
    segtree st1, st2;
    for(int i=0; i<n-1; i++){
        int a, b; cin >> a >> b;
        path1.push_back(P(a-i, b-i-1, -1));
        path2.push_back(P(a-(n-2-i), b-(n-2-i)-1, -1));
    }
    st1.build(path1);

    reverse(path2.begin(), path2.end());
    // for(P p:path2) cout << p.l << " " << p.r << " " << p.k << "\n";
    st2.build(path2);

    auto solve=[&](int a, int b, int c, int d, P p)->ll{
        b-=a, d-=c;
        if(p.k==-1){
            int x=b;
            x=max(x, p.l); x=min(x, p.r);
            return max(0, b-x)+max(0, x-d);
        }
        else{
            // cout << "jf " << max(0, b-p.l) << "+" << p.k < <"
            // cout << "Ppp " << p.l << " " << p.r << " " << p.k << '\n';
            return max(0, b-p.l)+p.k+max(0, p.r-d);
        }
    };

    while(q--){
        int op; cin >> op;
        if(op==1){
            int i, a, b; cin >> i >> a >> b;
            --i;
            st1.upd(i, P(a-i, b-i-1, -1));
            st2.upd(n-2-i, P(a-(n-2-i), b-(n-2-i)-1, -1));
        }
        else{
            int a, b, c, d; cin >> a >> b >> c >> d;
            --a, --c;
            if(a==c) cout << max(0, b-d) << "\n";
            if(a<c) cout << solve(a, b, c, d, st1.query(a, c)) << "\n";
            if(a>c) cout << solve(n-1-a, b, n-1-c, d, st2.query(n-1-a, n-1-c)) << '\n';
        }
    }
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 3 ms 536 KB Output is correct
12 Correct 4 ms 652 KB Output is correct
13 Correct 3 ms 588 KB Output is correct
14 Correct 3 ms 584 KB Output is correct
15 Correct 4 ms 628 KB Output is correct
16 Correct 3 ms 596 KB Output is correct
17 Correct 4 ms 624 KB Output is correct
18 Correct 4 ms 648 KB Output is correct
19 Correct 3 ms 596 KB Output is correct
20 Correct 5 ms 636 KB Output is correct
21 Correct 3 ms 588 KB Output is correct
22 Correct 3 ms 616 KB Output is correct
23 Correct 3 ms 596 KB Output is correct
24 Correct 3 ms 596 KB Output is correct
25 Correct 3 ms 596 KB Output is correct
26 Correct 3 ms 596 KB Output is correct
27 Correct 3 ms 596 KB Output is correct
28 Correct 3 ms 644 KB Output is correct
29 Correct 4 ms 640 KB Output is correct
30 Correct 4 ms 636 KB Output is correct
31 Correct 4 ms 640 KB Output is correct
32 Correct 3 ms 596 KB Output is correct
33 Correct 3 ms 684 KB Output is correct
34 Correct 3 ms 584 KB Output is correct
35 Correct 3 ms 596 KB Output is correct
36 Correct 4 ms 652 KB Output is correct
37 Correct 3 ms 596 KB Output is correct
38 Correct 3 ms 596 KB Output is correct
39 Correct 3 ms 584 KB Output is correct
40 Correct 4 ms 604 KB Output is correct
41 Runtime error 348 ms 524288 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3019 ms 105072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 3 ms 536 KB Output is correct
12 Correct 4 ms 652 KB Output is correct
13 Correct 3 ms 588 KB Output is correct
14 Correct 3 ms 584 KB Output is correct
15 Correct 4 ms 628 KB Output is correct
16 Correct 3 ms 596 KB Output is correct
17 Correct 4 ms 624 KB Output is correct
18 Correct 4 ms 648 KB Output is correct
19 Correct 3 ms 596 KB Output is correct
20 Correct 5 ms 636 KB Output is correct
21 Correct 3 ms 588 KB Output is correct
22 Correct 3 ms 616 KB Output is correct
23 Correct 3 ms 596 KB Output is correct
24 Correct 3 ms 596 KB Output is correct
25 Correct 3 ms 596 KB Output is correct
26 Correct 3 ms 596 KB Output is correct
27 Correct 3 ms 596 KB Output is correct
28 Correct 3 ms 644 KB Output is correct
29 Correct 4 ms 640 KB Output is correct
30 Correct 4 ms 636 KB Output is correct
31 Correct 4 ms 640 KB Output is correct
32 Correct 3 ms 596 KB Output is correct
33 Correct 3 ms 684 KB Output is correct
34 Correct 3 ms 584 KB Output is correct
35 Correct 3 ms 596 KB Output is correct
36 Correct 4 ms 652 KB Output is correct
37 Correct 3 ms 596 KB Output is correct
38 Correct 3 ms 596 KB Output is correct
39 Correct 3 ms 584 KB Output is correct
40 Correct 4 ms 604 KB Output is correct
41 Runtime error 348 ms 524288 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -