oj.uz

Submission #992420

# Submission time Handle Problem Language Result Execution time Memory
992420 2024-06-04T12:20:38 Z 79brue Escape Route 2 (JOI24_escape2) C++17
54 / 100
 482 ms 273040 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 1e18;

struct segTree{
    int minV[400002], minIdx[400002];

    void init(int i, int l, int r, int *A){
        if(l==r){
            minV[i] = A[l], minIdx[i] = l;
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, A);
        init(i*2+1, m+1, r, A);
        if(minV[i*2] <= minV[i*2+1]) minV[i] = minV[i*2], minIdx[i] = minIdx[i*2];
        else minV[i] = minV[i*2+1], minIdx[i] = minIdx[i*2+1];
    }

    pair<int, int> query(int i, int l, int r, int s, int e){
        if(r<s || e<l) return make_pair(INT_MAX, -1);
        if(s<=l && r<=e) return make_pair(minV[i], minIdx[i]);
        int m = (l+r)>>1;
        return min(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }
} tree;

struct dat{
    ll x, y;
    dat(){}
    dat(ll x, ll y): x(x), y(y){}
    bool operator<(const dat &r)const{
        if(x != r.x) return x < r.x;
        return y > r.y;
    }
    bool operator<(const ll &r)const{
        return x < r;
    }
};

int n; ll T;
vector<dat> arr[100002];
vector<dat> arrRev[100002];
int sz[100002];

vector<ll> sps[100002][20], spsRev[100002][20];

struct Query{
    int l, r, idx;
    Query(){}
    Query(int l, int r, int idx): l(l), r(r), idx(idx){}
};

int q;
vector<Query> queries[100002];
ll ans[300002];

int lRecent[100002], rRecent[100002];
vector<ll> lVec[100002], rVec[100002];

int main(){
    scanf("%d %lld", &n, &T);
    for(int i=1; i<n; i++){
        int s;
        scanf("%d", &s);

        vector<dat> vec;
        vec.resize(s);
        for(int j=0; j<s; j++) scanf("%lld %lld", &vec[j].x, &vec[j].y);

        sort(vec.begin(), vec.end());
        for(int j=0; j<s; j++){
            while(!arr[i].empty() && arr[i].back().y >= vec[j].y) arr[i].pop_back();
            arr[i].push_back(vec[j]);
        }
        sz[i] = (int)arr[i].size();

        arrRev[i+1] = arr[i];
        for(dat &p: arrRev[i+1]) swap(p.x, p.y);
    }
    tree.init(1, 1, n-1, sz);

    /// sps 채우기
    for(int i=1; i<n; i++) for(int j=0; j<sz[i]; j++) sps[i][0].push_back(arr[i][j].y);
    for(int d=1; d<20; d++){
        for(int i=1; i+(1<<d)<=n; i++) for(int j=0; j<sz[i]; j++){
            ll vT = sps[i][d-1][j], vtime = vT % T; vT -= vtime;
            int nxtX = i + (1<<(d-1));
            ll nxtT;
            if(arr[nxtX].back().x >= vtime)
                nxtT = vT + sps[nxtX][d-1][lower_bound(arr[nxtX].begin(), arr[nxtX].end(), dat(vtime, INF)) - arr[nxtX].begin()];
            else nxtT = vT + T + sps[nxtX][d-1][0];
            sps[i][d].push_back(nxtT);
        }
    }

    /// spsRev 채우기
    for(int i=2; i<=n; i++) for(int j=0; j<sz[i-1]; j++) spsRev[i][0].push_back(T-arrRev[i][j].y);
    for(int d=1; d<20; d++){
        for(int i=n; i-(1<<d)>=1; i--) for(int j=0; j<sz[i-1]; j++){
            ll vT = spsRev[i][d-1][j], vtime = vT % T; vT -= vtime;
            int nxtX = i - (1<<(d-1));
            ll nxtT;
            if(arrRev[nxtX][0].x <= T - vtime)
                nxtT = vT + spsRev[nxtX][d-1][upper_bound(arrRev[nxtX].begin(), arrRev[nxtX].end(), dat(T-vtime, -INF)) - arrRev[nxtX].begin() - 1];
            else nxtT = vT + T + spsRev[nxtX][d-1][sz[nxtX-1]-1];
            spsRev[i][d].push_back(nxtT);
        }
    }

    scanf("%d", &q);
    for(int i=1; i<=q; i++){
        int l, r;
        scanf("%d %d", &l, &r);
        int minIdx = tree.query(1, 1, n-1, l, r-1).second;
        queries[minIdx].push_back(Query(l, r, i));
    }

    ll qsum = 0;
    for(int m=1; m<n; m++) qsum += ll(sz[m]) * (ll)queries[m].size();
    assert(qsum <= 200'000'000LL);

    qsum = 0;
    for(int m=1; m<n; m++){
        for(Query p: queries[m]){
            int L = p.l, R = p.r;
            if(lRecent[L] != m) qsum += sz[m], lRecent[L] = m;
            if(rRecent[R] != m) qsum += sz[m], rRecent[R] = m;
        }
    }
    assert(qsum <= 10'000'000);
    for(int i=1; i<=n; i++) lRecent[i] = rRecent[i] = 0;

    for(int m=1; m<n; m++){
        for(Query p: queries[m]){
            int L = p.l, R = p.r;
            if(lRecent[L] != m){
                lRecent[L] = m;
                lVec[L].clear();
                for(int i=0; i<sz[m]; i++){
                    ll nowT = T - arrRev[m+1][i].x; int diff = m+1 - L, nowX = m+1;
                    for(int j=0; j<20; j++) if((diff>>j)&1){
                        ll vtime = nowT % T, vT = nowT - vtime, nxtT;
                        if(arrRev[nowX][0].x <= T - vtime)
                            nxtT = vT + spsRev[nowX][j][upper_bound(arrRev[nowX].begin(), arrRev[nowX].end(), dat(T-vtime, -INF)) - arrRev[nowX].begin() - 1];
                        else nxtT = vT + T + spsRev[nowX][j][sz[nowX-1]-1];
                        nowT = nxtT, nowX -= 1<<j;
                    }
                    lVec[L].push_back(nowT);
                }
            }
            if(rRecent[R] != m){
                rRecent[R] = m;
                rVec[R].clear();
                for(int i=0; i<sz[m]; i++){
                    ll nowT = arr[m][i].x; int diff = R-m, nowX = m;
                    for(int j=0; j<20; j++) if((diff>>j)&1){
                        ll vtime = nowT % T, vT = nowT - vtime, nxtT;
                        if(arr[nowX].back().x >= vtime)
                            nxtT = vT + sps[nowX][j][lower_bound(arr[nowX].begin(), arr[nowX].end(), dat(vtime, INF)) - arr[nowX].begin()];
                        else nxtT = vT + T + sps[nowX][j][0];
                        nowT = nxtT, nowX += 1<<j;
                    }
                    rVec[R].push_back(nowT);
                }
            }

            ll minV = LLONG_MAX;
            for(int i=0; i<sz[m]; i++){
                minV = min(minV, lVec[L][i] - (T - arrRev[m+1][i].x) + rVec[R][i] - arr[m][i].x - (arr[m][i].y - arr[m][i].x));
            }
            ans[p.idx] = minV;
        }
    }

    for(int i=1; i<=q; i++) printf("%lld\n", ans[i]);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     scanf("%d %lld", &n, &T);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%d", &s);
      |         ~~~~~^~~~~~~~~~
Main.cpp:72:37: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         for(int j=0; j<s; j++) scanf("%lld %lld", &vec[j].x, &vec[j].y);
      |                                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
Main.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 111196 KB Output is correct
2 Correct 66 ms 118988 KB Output is correct
3 Correct 108 ms 119892 KB Output is correct
4 Correct 142 ms 122388 KB Output is correct
5 Correct 116 ms 120144 KB Output is correct
6 Correct 159 ms 122452 KB Output is correct
7 Correct 144 ms 122552 KB Output is correct
8 Correct 115 ms 119888 KB Output is correct
9 Correct 148 ms 122448 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 111196 KB Output is correct
2 Correct 66 ms 118988 KB Output is correct
3 Correct 108 ms 119892 KB Output is correct
4 Correct 142 ms 122388 KB Output is correct
5 Correct 116 ms 120144 KB Output is correct
6 Correct 159 ms 122452 KB Output is correct
7 Correct 144 ms 122552 KB Output is correct
8 Correct 115 ms 119888 KB Output is correct
9 Correct 148 ms 122448 KB Output is correct
10 Correct 20 ms 111412 KB Output is correct
11 Correct 145 ms 120916 KB Output is correct
12 Correct 139 ms 120616 KB Output is correct
13 Correct 120 ms 120284 KB Output is correct
14 Correct 121 ms 120404 KB Output is correct
15 Correct 118 ms 120660 KB Output is correct
16 Correct 70 ms 119244 KB Output is correct
17 Correct 140 ms 121168 KB Output is correct
18 Correct 115 ms 120464 KB Output is correct
19 Correct 138 ms 121424 KB Output is correct
20 Correct 121 ms 120404 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 111196 KB Output is correct
2 Correct 66 ms 118988 KB Output is correct
3 Correct 108 ms 119892 KB Output is correct
4 Correct 142 ms 122388 KB Output is correct
5 Correct 116 ms 120144 KB Output is correct
6 Correct 159 ms 122452 KB Output is correct
7 Correct 144 ms 122552 KB Output is correct
8 Correct 115 ms 119888 KB Output is correct
9 Correct 148 ms 122448 KB Output is correct
10 Correct 315 ms 203088 KB Output is correct
11 Correct 438 ms 230996 KB Output is correct
12 Correct 437 ms 230996 KB Output is correct
13 Correct 395 ms 229236 KB Output is correct
14 Correct 480 ms 232016 KB Output is correct
15 Correct 441 ms 232020 KB Output is correct
16 Correct 333 ms 203984 KB Output is correct
17 Correct 469 ms 232016 KB Output is correct
18 Correct 262 ms 211128 KB Output is correct
19 Correct 255 ms 210956 KB Output is correct
20 Correct 273 ms 211792 KB Output is correct
21 Correct 260 ms 211788 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 111196 KB Output is correct
2 Correct 66 ms 118988 KB Output is correct
3 Correct 108 ms 119892 KB Output is correct
4 Correct 142 ms 122388 KB Output is correct
5 Correct 116 ms 120144 KB Output is correct
6 Correct 159 ms 122452 KB Output is correct
7 Correct 144 ms 122552 KB Output is correct
8 Correct 115 ms 119888 KB Output is correct
9 Correct 148 ms 122448 KB Output is correct
10 Correct 20 ms 111412 KB Output is correct
11 Correct 145 ms 120916 KB Output is correct
12 Correct 139 ms 120616 KB Output is correct
13 Correct 120 ms 120284 KB Output is correct
14 Correct 121 ms 120404 KB Output is correct
15 Correct 118 ms 120660 KB Output is correct
16 Correct 70 ms 119244 KB Output is correct
17 Correct 140 ms 121168 KB Output is correct
18 Correct 115 ms 120464 KB Output is correct
19 Correct 138 ms 121424 KB Output is correct
20 Correct 121 ms 120404 KB Output is correct
21 Correct 315 ms 203088 KB Output is correct
22 Correct 438 ms 230996 KB Output is correct
23 Correct 437 ms 230996 KB Output is correct
24 Correct 395 ms 229236 KB Output is correct
25 Correct 480 ms 232016 KB Output is correct
26 Correct 441 ms 232020 KB Output is correct
27 Correct 333 ms 203984 KB Output is correct
28 Correct 469 ms 232016 KB Output is correct
29 Correct 262 ms 211128 KB Output is correct
30 Correct 255 ms 210956 KB Output is correct
31 Correct 273 ms 211792 KB Output is correct
32 Correct 260 ms 211788 KB Output is correct
33 Correct 476 ms 170244 KB Output is correct
34 Correct 482 ms 170324 KB Output is correct
35 Correct 412 ms 159572 KB Output is correct
36 Correct 415 ms 159572 KB Output is correct
37 Correct 318 ms 173048 KB Output is correct
38 Correct 321 ms 173648 KB Output is correct
39 Correct 416 ms 192844 KB Output is correct
40 Correct 302 ms 153324 KB Output is correct
41 Correct 337 ms 171828 KB Output is correct
42 Correct 422 ms 193104 KB Output is correct
43 Correct 317 ms 158288 KB Output is correct
44 Correct 352 ms 160876 KB Output is correct
45 Correct 257 ms 177492 KB Output is correct
46 Correct 226 ms 158796 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 111192 KB Output is correct
2 Correct 19 ms 111196 KB Output is correct
3 Runtime error 175 ms 273040 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 111196 KB Output is correct
2 Correct 66 ms 118988 KB Output is correct
3 Correct 108 ms 119892 KB Output is correct
4 Correct 142 ms 122388 KB Output is correct
5 Correct 116 ms 120144 KB Output is correct
6 Correct 159 ms 122452 KB Output is correct
7 Correct 144 ms 122552 KB Output is correct
8 Correct 115 ms 119888 KB Output is correct
9 Correct 148 ms 122448 KB Output is correct
10 Correct 20 ms 111412 KB Output is correct
11 Correct 145 ms 120916 KB Output is correct
12 Correct 139 ms 120616 KB Output is correct
13 Correct 120 ms 120284 KB Output is correct
14 Correct 121 ms 120404 KB Output is correct
15 Correct 118 ms 120660 KB Output is correct
16 Correct 70 ms 119244 KB Output is correct
17 Correct 140 ms 121168 KB Output is correct
18 Correct 115 ms 120464 KB Output is correct
19 Correct 138 ms 121424 KB Output is correct
20 Correct 121 ms 120404 KB Output is correct
21 Correct 315 ms 203088 KB Output is correct
22 Correct 438 ms 230996 KB Output is correct
23 Correct 437 ms 230996 KB Output is correct
24 Correct 395 ms 229236 KB Output is correct
25 Correct 480 ms 232016 KB Output is correct
26 Correct 441 ms 232020 KB Output is correct
27 Correct 333 ms 203984 KB Output is correct
28 Correct 469 ms 232016 KB Output is correct
29 Correct 262 ms 211128 KB Output is correct
30 Correct 255 ms 210956 KB Output is correct
31 Correct 273 ms 211792 KB Output is correct
32 Correct 260 ms 211788 KB Output is correct
33 Correct 476 ms 170244 KB Output is correct
34 Correct 482 ms 170324 KB Output is correct
35 Correct 412 ms 159572 KB Output is correct
36 Correct 415 ms 159572 KB Output is correct
37 Correct 318 ms 173048 KB Output is correct
38 Correct 321 ms 173648 KB Output is correct
39 Correct 416 ms 192844 KB Output is correct
40 Correct 302 ms 153324 KB Output is correct
41 Correct 337 ms 171828 KB Output is correct
42 Correct 422 ms 193104 KB Output is correct
43 Correct 317 ms 158288 KB Output is correct
44 Correct 352 ms 160876 KB Output is correct
45 Correct 257 ms 177492 KB Output is correct
46 Correct 226 ms 158796 KB Output is correct
47 Correct 19 ms 111192 KB Output is correct
48 Correct 19 ms 111196 KB Output is correct
49 Runtime error 175 ms 273040 KB Execution killed with signal 6
50 Halted 0 ms 0 KB -