Submission #992420

#	Time	Username	Problem	Language	Result	Execution time	Memory
992420		79brue	Escape Route 2 (JOI24_escape2)	C++17	54 / 100	482 ms	273040 KiB

Main

#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 (stderr)

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 / 6
• Subtask 2: 8 / 8
• Subtask 3: 17 / 17
• Subtask 4: 23 / 23
• Subtask 5: 0 / 36
• Subtask 6: 0 / 10