oj.uz

답안 #992941

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
992941 2024-06-05T08:28:30 Z 79brue Escape Route 2 (JOI24_escape2) C++17
54 / 100
 328 ms 240208 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 1e18;
const int DEPTH = 17;

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;
    }
};

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

int n, q, K; ll T;
dat arr[100002], arrRev[100002];
int S[100002], E[100002], sz[100002], from[100002];

int nxtR[100002], dayR[100002], nxtL[100002], dayL[100002];
vector<int> childL[100002], childR[100002]; /// 왼쪽이 루트인 트리 / 오른쪽이 루트인 트리

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

int listX[100002], listD[100002];
int pcnt = 0;
void dfsL(int x){
    listX[from[x]] = x;
    ql[x].reserve((int)queries[from[x]].size());
    for(Query &p: queries[from[x]]){
        ql[x].push_back((listD[from[x]] - listD[p.l]) * T + arr[x].x - arr[listX[p.l]].x);
    }
    listD[from[x]+1] = listD[from[x]];
    for(int y: childL[x]){
        if(arrRev[x].x > arrRev[y].y) listD[from[x]+1]++;
        dfsL(y);
        if(arrRev[x].x > arrRev[y].y) listD[from[x]+1]--;
    }
}
void dfsR(int x){
    listX[from[x]] = x;
    for(int i=0; i<(int)queries[from[x]].size(); i++){
        Query p = queries[from[x]][i];
        ll qlv = ql[x][i], qrv = (listD[from[x]] - listD[p.r-1]) * T + arr[listX[p.r-1]].y - arr[x].y;
        ans[p.idx] = min(ans[p.idx], qlv + qrv + arr[x].y - arr[x].x);
    }
    listD[from[x]-1] = listD[from[x]];
    for(int y: childR[x]){
        if(arr[x].x < arr[y].y) listD[from[x]-1]++;
        dfsR(y);
        if(arr[x].x < arr[y].y) listD[from[x]-1]--;
    }
}

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());

        vector<dat> vec2;
        for(int j=0; j<s; j++){
            while(!vec2.empty() && vec2.back().y >= vec[j].y) vec2.pop_back();
            vec2.push_back(vec[j]);
        }
        sz[i] = (int)vec2.size();

        S[i] = E[i-1] + 1, E[i] = S[i] + sz[i] - 1;
        for(int j=0; j<sz[i]; j++) arr[S[i]+j] = vec2[j];
        for(int j=S[i]; j<=E[i]; j++) arrRev[j] = dat(arr[j].y, arr[j].x), from[j] = i;
    }
    tree.init(1, 1, n-1, sz);

    for(int d=1; d<=n-2; d++){
        for(int i=S[d]; i<=E[d]; i++){
            int L = S[d+1], R = E[d+1];
            if(arr[R].x >= arr[i].y) nxtR[i] = lower_bound(arr+L, arr+R+1, dat(arr[i].y, INF)) - arr;
            else nxtR[i] = L, dayR[i] = 1;
            childR[nxtR[i]].push_back(i);
        }
    }
    for(int d=3; d<=n; d++){
        for(int i=S[d-1]; i<=E[d-1]; i++){
            int L = S[d-2], R = E[d-2];
            if(arrRev[L].x <= arrRev[i].y) nxtL[i] = upper_bound(arrRev+L, arrRev+R+1, dat(arrRev[i].y, -INF)) - arrRev - 1;
            else nxtL[i] = R, dayL[i] = 1;
            childL[nxtL[i]].push_back(i);
        }
    }

    ll qsum = 0;

    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));
        ans[i] = LLONG_MAX;
        qsum += sz[minIdx];
    }
    assert(qsum <= 27'000'000);

    listD[1] = 0;
    for(int i=S[1]; i<=E[1]; i++) dfsL(i);
    listD[n-1] = 0;
    for(int i=S[n-1]; i<=E[n-1]; i++) dfsR(i);

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

Compilation message

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

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 52 ms 28092 KB Output is correct
3 Correct 124 ms 27984 KB Output is correct
4 Correct 116 ms 30548 KB Output is correct
5 Correct 92 ms 27984 KB Output is correct
6 Correct 117 ms 30548 KB Output is correct
7 Correct 123 ms 30808 KB Output is correct
8 Correct 92 ms 28164 KB Output is correct
9 Correct 118 ms 30544 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 52 ms 28092 KB Output is correct
3 Correct 124 ms 27984 KB Output is correct
4 Correct 116 ms 30548 KB Output is correct
5 Correct 92 ms 27984 KB Output is correct
6 Correct 117 ms 30548 KB Output is correct
7 Correct 123 ms 30808 KB Output is correct
8 Correct 92 ms 28164 KB Output is correct
9 Correct 118 ms 30544 KB Output is correct
10 Correct 3 ms 18780 KB Output is correct
11 Correct 111 ms 39280 KB Output is correct
12 Correct 111 ms 38936 KB Output is correct
13 Correct 113 ms 36476 KB Output is correct
14 Correct 106 ms 36432 KB Output is correct
15 Correct 144 ms 29524 KB Output is correct
16 Correct 53 ms 31920 KB Output is correct
17 Correct 113 ms 30288 KB Output is correct
18 Correct 104 ms 29576 KB Output is correct
19 Correct 113 ms 30032 KB Output is correct
20 Correct 119 ms 29648 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 52 ms 28092 KB Output is correct
3 Correct 124 ms 27984 KB Output is correct
4 Correct 116 ms 30548 KB Output is correct
5 Correct 92 ms 27984 KB Output is correct
6 Correct 117 ms 30548 KB Output is correct
7 Correct 123 ms 30808 KB Output is correct
8 Correct 92 ms 28164 KB Output is correct
9 Correct 118 ms 30544 KB Output is correct
10 Correct 152 ms 44596 KB Output is correct
11 Correct 225 ms 52320 KB Output is correct
12 Correct 238 ms 52308 KB Output is correct
13 Correct 185 ms 49492 KB Output is correct
14 Correct 255 ms 52564 KB Output is correct
15 Correct 247 ms 52564 KB Output is correct
16 Correct 168 ms 44648 KB Output is correct
17 Correct 227 ms 52452 KB Output is correct
18 Correct 93 ms 41812 KB Output is correct
19 Correct 88 ms 41316 KB Output is correct
20 Correct 106 ms 42024 KB Output is correct
21 Correct 100 ms 42068 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 52 ms 28092 KB Output is correct
3 Correct 124 ms 27984 KB Output is correct
4 Correct 116 ms 30548 KB Output is correct
5 Correct 92 ms 27984 KB Output is correct
6 Correct 117 ms 30548 KB Output is correct
7 Correct 123 ms 30808 KB Output is correct
8 Correct 92 ms 28164 KB Output is correct
9 Correct 118 ms 30544 KB Output is correct
10 Correct 3 ms 18780 KB Output is correct
11 Correct 111 ms 39280 KB Output is correct
12 Correct 111 ms 38936 KB Output is correct
13 Correct 113 ms 36476 KB Output is correct
14 Correct 106 ms 36432 KB Output is correct
15 Correct 144 ms 29524 KB Output is correct
16 Correct 53 ms 31920 KB Output is correct
17 Correct 113 ms 30288 KB Output is correct
18 Correct 104 ms 29576 KB Output is correct
19 Correct 113 ms 30032 KB Output is correct
20 Correct 119 ms 29648 KB Output is correct
21 Correct 152 ms 44596 KB Output is correct
22 Correct 225 ms 52320 KB Output is correct
23 Correct 238 ms 52308 KB Output is correct
24 Correct 185 ms 49492 KB Output is correct
25 Correct 255 ms 52564 KB Output is correct
26 Correct 247 ms 52564 KB Output is correct
27 Correct 168 ms 44648 KB Output is correct
28 Correct 227 ms 52452 KB Output is correct
29 Correct 93 ms 41812 KB Output is correct
30 Correct 88 ms 41316 KB Output is correct
31 Correct 106 ms 42024 KB Output is correct
32 Correct 100 ms 42068 KB Output is correct
33 Correct 213 ms 50512 KB Output is correct
34 Correct 288 ms 50516 KB Output is correct
35 Correct 199 ms 46164 KB Output is correct
36 Correct 199 ms 46160 KB Output is correct
37 Correct 184 ms 37864 KB Output is correct
38 Correct 154 ms 39252 KB Output is correct
39 Correct 210 ms 45396 KB Output is correct
40 Correct 161 ms 36080 KB Output is correct
41 Correct 178 ms 40016 KB Output is correct
42 Correct 216 ms 45652 KB Output is correct
43 Correct 163 ms 36180 KB Output is correct
44 Correct 188 ms 38480 KB Output is correct
45 Correct 93 ms 35320 KB Output is correct
46 Correct 81 ms 30032 KB Output is correct

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 2 ms 18780 KB Output is correct
3 Correct 328 ms 240140 KB Output is correct
4 Correct 274 ms 240208 KB Output is correct
5 Correct 285 ms 240112 KB Output is correct
6 Correct 281 ms 239384 KB Output is correct
7 Correct 294 ms 239440 KB Output is correct
8 Correct 166 ms 129740 KB Output is correct
9 Correct 55 ms 27216 KB Output is correct
10 Runtime error 48 ms 44680 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 52 ms 28092 KB Output is correct
3 Correct 124 ms 27984 KB Output is correct
4 Correct 116 ms 30548 KB Output is correct
5 Correct 92 ms 27984 KB Output is correct
6 Correct 117 ms 30548 KB Output is correct
7 Correct 123 ms 30808 KB Output is correct
8 Correct 92 ms 28164 KB Output is correct
9 Correct 118 ms 30544 KB Output is correct
10 Correct 3 ms 18780 KB Output is correct
11 Correct 111 ms 39280 KB Output is correct
12 Correct 111 ms 38936 KB Output is correct
13 Correct 113 ms 36476 KB Output is correct
14 Correct 106 ms 36432 KB Output is correct
15 Correct 144 ms 29524 KB Output is correct
16 Correct 53 ms 31920 KB Output is correct
17 Correct 113 ms 30288 KB Output is correct
18 Correct 104 ms 29576 KB Output is correct
19 Correct 113 ms 30032 KB Output is correct
20 Correct 119 ms 29648 KB Output is correct
21 Correct 152 ms 44596 KB Output is correct
22 Correct 225 ms 52320 KB Output is correct
23 Correct 238 ms 52308 KB Output is correct
24 Correct 185 ms 49492 KB Output is correct
25 Correct 255 ms 52564 KB Output is correct
26 Correct 247 ms 52564 KB Output is correct
27 Correct 168 ms 44648 KB Output is correct
28 Correct 227 ms 52452 KB Output is correct
29 Correct 93 ms 41812 KB Output is correct
30 Correct 88 ms 41316 KB Output is correct
31 Correct 106 ms 42024 KB Output is correct
32 Correct 100 ms 42068 KB Output is correct
33 Correct 213 ms 50512 KB Output is correct
34 Correct 288 ms 50516 KB Output is correct
35 Correct 199 ms 46164 KB Output is correct
36 Correct 199 ms 46160 KB Output is correct
37 Correct 184 ms 37864 KB Output is correct
38 Correct 154 ms 39252 KB Output is correct
39 Correct 210 ms 45396 KB Output is correct
40 Correct 161 ms 36080 KB Output is correct
41 Correct 178 ms 40016 KB Output is correct
42 Correct 216 ms 45652 KB Output is correct
43 Correct 163 ms 36180 KB Output is correct
44 Correct 188 ms 38480 KB Output is correct
45 Correct 93 ms 35320 KB Output is correct
46 Correct 81 ms 30032 KB Output is correct
47 Correct 3 ms 18780 KB Output is correct
48 Correct 2 ms 18780 KB Output is correct
49 Correct 328 ms 240140 KB Output is correct
50 Correct 274 ms 240208 KB Output is correct
51 Correct 285 ms 240112 KB Output is correct
52 Correct 281 ms 239384 KB Output is correct
53 Correct 294 ms 239440 KB Output is correct
54 Correct 166 ms 129740 KB Output is correct
55 Correct 55 ms 27216 KB Output is correct
56 Runtime error 48 ms 44680 KB Execution killed with signal 6
57 Halted 0 ms 0 KB -