Submission #992974

#	Time	Username	Problem	Language	Result	Execution time	Memory
992974		79brue	Escape Route 2 (JOI24_escape2)	C++17	100 / 100	690 ms	358364 KiB

Main

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

map<pair<int, int>, int> queryMap;
int prvQuery[300002];

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

        if(queryMap.count(make_pair(l, r))){
            prvQuery[i] = queryMap[make_pair(l, r)];
            continue;
        }
        queryMap[make_pair(l, r)] = i;

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

    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++) if(prvQuery[i]) ans[i] = ans[prvQuery[i]];

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

Compilation message (stderr)

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

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 17 / 17
• Subtask 4: 23 / 23
• Subtask 5: 36 / 36
• Subtask 6: 10 / 10