oj.uz

Submission #992374

# Submission time Handle Problem Language Result Execution time Memory
992374 2024-06-04T10:56:25 Z 79brue Escape Route 2 (JOI24_escape2) C++17
31 / 100
 473 ms 332156 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 <= 1'200'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 111192 KB Output is correct
2 Correct 65 ms 119900 KB Output is correct
3 Correct 110 ms 119888 KB Output is correct
4 Correct 149 ms 122532 KB Output is correct
5 Correct 117 ms 120148 KB Output is correct
6 Correct 147 ms 122456 KB Output is correct
7 Correct 157 ms 122744 KB Output is correct
8 Correct 113 ms 119888 KB Output is correct
9 Correct 143 ms 122448 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 111192 KB Output is correct
2 Correct 65 ms 119900 KB Output is correct
3 Correct 110 ms 119888 KB Output is correct
4 Correct 149 ms 122532 KB Output is correct
5 Correct 117 ms 120148 KB Output is correct
6 Correct 147 ms 122456 KB Output is correct
7 Correct 157 ms 122744 KB Output is correct
8 Correct 113 ms 119888 KB Output is correct
9 Correct 143 ms 122448 KB Output is correct
10 Correct 17 ms 111196 KB Output is correct
11 Correct 136 ms 120660 KB Output is correct
12 Correct 140 ms 120656 KB Output is correct
13 Correct 119 ms 120392 KB Output is correct
14 Correct 140 ms 120544 KB Output is correct
15 Correct 116 ms 120660 KB Output is correct
16 Correct 65 ms 118208 KB Output is correct
17 Correct 133 ms 121168 KB Output is correct
18 Correct 112 ms 120460 KB Output is correct
19 Correct 184 ms 121424 KB Output is correct
20 Correct 119 ms 120400 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 111192 KB Output is correct
2 Correct 65 ms 119900 KB Output is correct
3 Correct 110 ms 119888 KB Output is correct
4 Correct 149 ms 122532 KB Output is correct
5 Correct 117 ms 120148 KB Output is correct
6 Correct 147 ms 122456 KB Output is correct
7 Correct 157 ms 122744 KB Output is correct
8 Correct 113 ms 119888 KB Output is correct
9 Correct 143 ms 122448 KB Output is correct
10 Correct 313 ms 203076 KB Output is correct
11 Correct 444 ms 230996 KB Output is correct
12 Correct 473 ms 230956 KB Output is correct
13 Correct 378 ms 229312 KB Output is correct
14 Correct 444 ms 232180 KB Output is correct
15 Correct 422 ms 232016 KB Output is correct
16 Correct 322 ms 203856 KB Output is correct
17 Correct 441 ms 232024 KB Output is correct
18 Correct 256 ms 211028 KB Output is correct
19 Correct 242 ms 211024 KB Output is correct
20 Correct 263 ms 211796 KB Output is correct
21 Correct 249 ms 211792 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 111192 KB Output is correct
2 Correct 65 ms 119900 KB Output is correct
3 Correct 110 ms 119888 KB Output is correct
4 Correct 149 ms 122532 KB Output is correct
5 Correct 117 ms 120148 KB Output is correct
6 Correct 147 ms 122456 KB Output is correct
7 Correct 157 ms 122744 KB Output is correct
8 Correct 113 ms 119888 KB Output is correct
9 Correct 143 ms 122448 KB Output is correct
10 Correct 17 ms 111196 KB Output is correct
11 Correct 136 ms 120660 KB Output is correct
12 Correct 140 ms 120656 KB Output is correct
13 Correct 119 ms 120392 KB Output is correct
14 Correct 140 ms 120544 KB Output is correct
15 Correct 116 ms 120660 KB Output is correct
16 Correct 65 ms 118208 KB Output is correct
17 Correct 133 ms 121168 KB Output is correct
18 Correct 112 ms 120460 KB Output is correct
19 Correct 184 ms 121424 KB Output is correct
20 Correct 119 ms 120400 KB Output is correct
21 Correct 313 ms 203076 KB Output is correct
22 Correct 444 ms 230996 KB Output is correct
23 Correct 473 ms 230956 KB Output is correct
24 Correct 378 ms 229312 KB Output is correct
25 Correct 444 ms 232180 KB Output is correct
26 Correct 422 ms 232016 KB Output is correct
27 Correct 322 ms 203856 KB Output is correct
28 Correct 441 ms 232024 KB Output is correct
29 Correct 256 ms 211028 KB Output is correct
30 Correct 242 ms 211024 KB Output is correct
31 Correct 263 ms 211796 KB Output is correct
32 Correct 249 ms 211792 KB Output is correct
33 Runtime error 315 ms 332156 KB Execution killed with signal 6
34 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 111196 KB Output is correct
2 Correct 22 ms 111196 KB Output is correct
3 Runtime error 173 ms 273236 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 111192 KB Output is correct
2 Correct 65 ms 119900 KB Output is correct
3 Correct 110 ms 119888 KB Output is correct
4 Correct 149 ms 122532 KB Output is correct
5 Correct 117 ms 120148 KB Output is correct
6 Correct 147 ms 122456 KB Output is correct
7 Correct 157 ms 122744 KB Output is correct
8 Correct 113 ms 119888 KB Output is correct
9 Correct 143 ms 122448 KB Output is correct
10 Correct 17 ms 111196 KB Output is correct
11 Correct 136 ms 120660 KB Output is correct
12 Correct 140 ms 120656 KB Output is correct
13 Correct 119 ms 120392 KB Output is correct
14 Correct 140 ms 120544 KB Output is correct
15 Correct 116 ms 120660 KB Output is correct
16 Correct 65 ms 118208 KB Output is correct
17 Correct 133 ms 121168 KB Output is correct
18 Correct 112 ms 120460 KB Output is correct
19 Correct 184 ms 121424 KB Output is correct
20 Correct 119 ms 120400 KB Output is correct
21 Correct 313 ms 203076 KB Output is correct
22 Correct 444 ms 230996 KB Output is correct
23 Correct 473 ms 230956 KB Output is correct
24 Correct 378 ms 229312 KB Output is correct
25 Correct 444 ms 232180 KB Output is correct
26 Correct 422 ms 232016 KB Output is correct
27 Correct 322 ms 203856 KB Output is correct
28 Correct 441 ms 232024 KB Output is correct
29 Correct 256 ms 211028 KB Output is correct
30 Correct 242 ms 211024 KB Output is correct
31 Correct 263 ms 211796 KB Output is correct
32 Correct 249 ms 211792 KB Output is correct
33 Runtime error 315 ms 332156 KB Execution killed with signal 6
34 Halted 0 ms 0 KB -