oj.uz

Submission #414935

# Submission time Handle Problem Language Result Execution time Memory
414935 2021-05-31T10:46:44 Z Pro_ktmr Bitaro, who Leaps through Time (JOI19_timeleap) C++17
100 / 100
 2643 ms 107476 KB 
#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };

template<typename T>
struct SegmentTree{
private:
    int N;
    vector<T> node;
    function<T(T, T)> F;
    T E;
public:
    void init(int n, function<T(T, T)> f, T e, T def){
        F = f;
        E = e;
        N = 1;
        while(N < n) N = (N<<1);
        node.assign(2*N-1, e);
        for(int i=0; i<n; i++) node[N-1+i] = def;
        for(int i=N-2; i>=0; i--) node[i] = F(node[(i<<1)+1], node[(i<<1)+2]);
    }
    T& operator [](int a){
        return node[N-1+a];
    }
    void update(int a, T x){
        a += N-1;
        node[a] = x;
        while(a > 0){
            a = (a-1)>>1;
            node[a] = F(node[(a<<1)+1], node[(a<<1)+2]);
        }
    }
    T query(int a, int b, int k=0, int l=0, int r=-1){
        if(r == -1) r = N;
        if(b <= l || r <= a) return E;
        if(a <= l && r <= b) return node[k];
        return F(query(a, b, (k<<1)+1, l, (l+r)>>1), query(a, b, (k<<1)+2, (l+r)>>1, r));
    }
};

struct Gate{
    bool e = false;
    ll A, B, c, t;
    friend Gate operator*(Gate &l, Gate &r){
        if(l.e) return r;
        if(r.e) return l;
        Gate ret;
        ll ok = l.B+1;
        ll ng = l.A;
        while(ok-ng > 1){
            ll m = (ok+ng) / 2;
            if(l.f(m).first + r.f(l.f(m).second).first >
                l.f(l.A).first + r.f(l.f(l.A).second).first){
                ok = m;
            }
            else{
                ng = m;
            }
        }
        ret.B = ng;

        ok = ret.B+1;
        ng = l.A;
        while(ok-ng > 1){
            ll m = (ok+ng) / 2;
            if(r.f(l.f(m).second).second > r.f(l.f(l.A).second).second){
                ok = m;
            }
            else{
                ng = m;
            }
        }
        ret.A = ng;

        ret.c = l.c + r.f(l.t).first;
        ret.t = r.f(l.t).second;
        return ret;
    }
    pair<ll, ll> f(ll x){
        if(x < A) return { c,t };
        if(x < B) return { c,t+x-A };
        return { c+x-B,t+B-A };
    }
};

int N, Q;
ll L[300000], R[300000];
SegmentTree<Gate> stL, stR;

void print(){
    return;
    int l = 6;
    int r = 18;
    cout << "PRINT 0" << endl;
    cout << stL[0].A << " " << stL[0].B << " " << stL[0].c << " " << stL[0].t << endl;
    for(int i=r; i>=l; i--){
        cout << i << ": " << stL[0].f(i).first << " " << stL[0].f(i).second << endl;
    }
    cout << "PRINT 1" << endl;
    cout << stL[1].A << " " << stL[1].B << " " << stL[1].c << " " << stL[1].t << endl;
    for(int i=r; i>=l; i--){
        cout << i << ": " << stL[1].f(i).first << " " << stL[1].f(i).second << endl;
    }
    cout << "PRINT [0,2)" << endl;
    cout << stL.query(0, 2).A << " " << stL.query(0, 2).B << " " << stL.query(0, 2).c << " " << stL.query(0, 2).t << endl;
    for(int i=r; i>=l; i--){
        cout << i << ": " << stL.query(0, 2).f(i).first << " " << stL.query(0, 2).f(i).second << endl;
    }
    cout << "PRINT 2" << endl;
    cout << stL[2].A << " " << stL[2].B << " " << stL[2].c << " " << stL[2].t << endl;
    for(int i=r; i>=l; i--){
        cout << i << ": " << stL[2].f(i).first << " " << stL[2].f(i).second << endl;
    }
    cout << "PRINT [0,3)" << endl;
    cout << stL.query(0, 3).A << " " << stL.query(0, 3).B << " " << stL.query(0, 3).c << " " << stL.query(0, 3).t << endl;
    for(int i=r; i>=l; i--){
        cout << i << ": " << stL.query(0, 3).f(i).first << " " << stL.query(0, 3).f(i).second << endl;
    }
    return;
    cout << "PRINT [2,4)" << endl;
    cout << stL.query(2, 4).A << " " << stL.query(2, 4).B << " " << stL.query(2, 4).c << " " << stL.query(2, 4).t << endl;
    for(int i=6; i>=l; i--){
        cout << i << ": " << stL.query(2, 4).f(i).first << " " << stL.query(2, 4).f(i).second << endl;
    }
}

void update(int i){
    stL.update(i, { false,L[i]-i, R[i]-i-1,0,L[i]-i });
    stR.update(N-2-i, { false,L[i]-(N-2-i), R[i]-(N-2-i)-1,0,L[i]-(N-2-i) });
}

signed main(){
    cin >> N >> Q;
    rep(i, N-1) cin >> L[i] >> R[i];

    stL.init(N-1, [](Gate l, Gate r){ return l*r; }, { true,0,0,0,0 }, { true,0,0,0,0 });
    stR.init(N-1, [](Gate l, Gate r){ return l*r; }, { true,0,0,0,0 }, { true,0,0,0,0 });
    rep(i, N-1){
        update(i);
    }

    print();

    rep(i, Q){
        int t;
        cin >> t;
        if(t == 1){
            int p;
            cin >> p;
            p--;
            cin >> L[p] >> R[p];
            update(p);
            print();
        }
        else{
            ll s, t1, g, t2;
            cin >> s >> t1 >> g >> t2;
            s--; g--;
            if(s < g){
                t1 -= s;
                t2 -= g;
                Gate gate = stL.query(s, g);
                ll c = gate.f(t1).first;
                ll t = gate.f(t1).second;
                c += max(0LL, t-t2);
                cout << c << endl;
            }
            else if(s > g){
                t1 -= N-1-s;
                t2 -= N-1-g;
                Gate gate = stR.query(N-1-s, N-1-g);
                ll c = gate.f(t1).first;
                ll t = gate.f(t1).second;
                c += max(0LL, t-t2);
                cout << c << endl;
            }
            else{
                cout << max(0LL, t1-t2) << endl;
            }
        }
    }
}

/*
5 1
10 18
8 16
4 12
13 15
2 2 17 5 18
*/

Compilation message

timeleap.cpp: In function 'int main()':
timeleap.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
timeleap.cpp:147:5: note: in expansion of macro 'rep'
  147 |     rep(i, N-1) cin >> L[i] >> R[i];
      |     ^~~
timeleap.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
timeleap.cpp:151:5: note: in expansion of macro 'rep'
  151 |     rep(i, N-1){
      |     ^~~
timeleap.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
timeleap.cpp:157:5: note: in expansion of macro 'rep'
  157 |     rep(i, Q){
      |     ^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 8 ms 460 KB Output is correct
12 Correct 8 ms 460 KB Output is correct
13 Correct 6 ms 460 KB Output is correct
14 Correct 8 ms 460 KB Output is correct
15 Correct 8 ms 460 KB Output is correct
16 Correct 7 ms 536 KB Output is correct
17 Correct 8 ms 436 KB Output is correct
18 Correct 8 ms 496 KB Output is correct
19 Correct 8 ms 500 KB Output is correct
20 Correct 7 ms 424 KB Output is correct
21 Correct 7 ms 436 KB Output is correct
22 Correct 5 ms 460 KB Output is correct
23 Correct 7 ms 460 KB Output is correct
24 Correct 6 ms 460 KB Output is correct
25 Correct 7 ms 460 KB Output is correct
26 Correct 6 ms 540 KB Output is correct
27 Correct 5 ms 460 KB Output is correct
28 Correct 8 ms 512 KB Output is correct
29 Correct 5 ms 496 KB Output is correct
30 Correct 5 ms 460 KB Output is correct
31 Correct 7 ms 460 KB Output is correct
32 Correct 7 ms 460 KB Output is correct
33 Correct 6 ms 460 KB Output is correct
34 Correct 6 ms 448 KB Output is correct
35 Correct 6 ms 540 KB Output is correct
36 Correct 7 ms 460 KB Output is correct
37 Correct 8 ms 468 KB Output is correct
38 Correct 6 ms 440 KB Output is correct
39 Correct 6 ms 460 KB Output is correct
40 Correct 8 ms 460 KB Output is correct
41 Correct 1 ms 204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2419 ms 106440 KB Output is correct
2 Correct 2354 ms 64920 KB Output is correct
3 Correct 2360 ms 64868 KB Output is correct
4 Correct 2491 ms 64528 KB Output is correct
5 Correct 2457 ms 106392 KB Output is correct
6 Correct 2469 ms 106248 KB Output is correct
7 Correct 2284 ms 106476 KB Output is correct
8 Correct 2292 ms 107260 KB Output is correct
9 Correct 2125 ms 64912 KB Output is correct
10 Correct 2430 ms 106460 KB Output is correct
11 Correct 2389 ms 106436 KB Output is correct
12 Correct 2519 ms 107212 KB Output is correct
13 Correct 2643 ms 107476 KB Output is correct
14 Correct 1 ms 204 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 8 ms 460 KB Output is correct
12 Correct 8 ms 460 KB Output is correct
13 Correct 6 ms 460 KB Output is correct
14 Correct 8 ms 460 KB Output is correct
15 Correct 8 ms 460 KB Output is correct
16 Correct 7 ms 536 KB Output is correct
17 Correct 8 ms 436 KB Output is correct
18 Correct 8 ms 496 KB Output is correct
19 Correct 8 ms 500 KB Output is correct
20 Correct 7 ms 424 KB Output is correct
21 Correct 7 ms 436 KB Output is correct
22 Correct 5 ms 460 KB Output is correct
23 Correct 7 ms 460 KB Output is correct
24 Correct 6 ms 460 KB Output is correct
25 Correct 7 ms 460 KB Output is correct
26 Correct 6 ms 540 KB Output is correct
27 Correct 5 ms 460 KB Output is correct
28 Correct 8 ms 512 KB Output is correct
29 Correct 5 ms 496 KB Output is correct
30 Correct 5 ms 460 KB Output is correct
31 Correct 7 ms 460 KB Output is correct
32 Correct 7 ms 460 KB Output is correct
33 Correct 6 ms 460 KB Output is correct
34 Correct 6 ms 448 KB Output is correct
35 Correct 6 ms 540 KB Output is correct
36 Correct 7 ms 460 KB Output is correct
37 Correct 8 ms 468 KB Output is correct
38 Correct 6 ms 440 KB Output is correct
39 Correct 6 ms 460 KB Output is correct
40 Correct 8 ms 460 KB Output is correct
41 Correct 1 ms 204 KB Output is correct
42 Correct 2419 ms 106440 KB Output is correct
43 Correct 2354 ms 64920 KB Output is correct
44 Correct 2360 ms 64868 KB Output is correct
45 Correct 2491 ms 64528 KB Output is correct
46 Correct 2457 ms 106392 KB Output is correct
47 Correct 2469 ms 106248 KB Output is correct
48 Correct 2284 ms 106476 KB Output is correct
49 Correct 2292 ms 107260 KB Output is correct
50 Correct 2125 ms 64912 KB Output is correct
51 Correct 2430 ms 106460 KB Output is correct
52 Correct 2389 ms 106436 KB Output is correct
53 Correct 2519 ms 107212 KB Output is correct
54 Correct 2643 ms 107476 KB Output is correct
55 Correct 1 ms 204 KB Output is correct
56 Correct 2447 ms 103180 KB Output is correct
57 Correct 2518 ms 61428 KB Output is correct
58 Correct 2270 ms 103488 KB Output is correct
59 Correct 2404 ms 103592 KB Output is correct
60 Correct 2282 ms 61780 KB Output is correct
61 Correct 2382 ms 103900 KB Output is correct
62 Correct 2419 ms 103824 KB Output is correct
63 Correct 2592 ms 103824 KB Output is correct
64 Correct 2461 ms 104080 KB Output is correct
65 Correct 2348 ms 103432 KB Output is correct
66 Correct 1985 ms 103452 KB Output is correct
67 Correct 2053 ms 103888 KB Output is correct
68 Correct 1908 ms 102636 KB Output is correct
69 Correct 1981 ms 104216 KB Output is correct
70 Correct 1849 ms 61868 KB Output is correct
71 Correct 2155 ms 61132 KB Output is correct
72 Correct 2270 ms 102524 KB Output is correct
73 Correct 2315 ms 103468 KB Output is correct
74 Correct 2333 ms 103556 KB Output is correct
75 Correct 2354 ms 103664 KB Output is correct
76 Correct 2332 ms 104288 KB Output is correct
77 Correct 1 ms 204 KB Output is correct