Submission #741304

#	Time	Username	Problem	Language	Result	Execution time	Memory
741304		Username4132	Passport (JOI23_passport)	C++14	100 / 100	305 ms	22472 KiB

passport

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define PB push_back
#define F first
#define S second

const int MAXN=200010, INF=1e7;
int n, q, x, dl[MAXN], dr[MAXN], ans[2*MAXN], order[MAXN];
vector<pii> low[MAXN];
pii arr[MAXN], ext[2*MAXN];

template<typename T>
void build(T* tr){
    dforn(i, n) tr[i]=min(tr[i<<1], tr[i<<1|1]);
}

template<typename T>
T query(int l, int r, T* tr, T ret){
    for(l+=n, r+=n; l<r; l>>=1, r>>=1){
        if(l&1) ret=min(ret, tr[l++]);
        if(r&1) ret=min(ret, tr[--r]);
    }
    return ret;
}

template<typename T>
void modify(int p, T value, T* tr){
    for(p+=n, tr[p]=value; p>1; p>>=1) tr[p>>1]=min(tr[p], tr[p^1]);
}

struct segment{
    segment(){
        forn(i, n) low[arr[i].S-1].PB({arr[i].F-1, i});
        forn(i, n) sort(low[i].begin(), low[i].end(), greater<pii>());
        forn(i, n) ext[i+n]={(low[i].empty()? INF : low[i].back().F), i};
        build(ext);
    }
    int extract(int p){
        pii pos = query(p, n, ext, {INF, INF});
        if(pos.F<=p){
            int ret = low[pos.S].back().S;
            low[pos.S].pop_back();
            modify(pos.S, {(low[pos.S].empty()? INF : low[pos.S].back().F), pos.S}, ext);
            return ret;
        }
        else return -1;
    }
};


void bfs(int start, int* dis){
    segment seg;
    queue<int> Q;
    forn(i, n) dis[i]=INF;
    dis[start]=-1;
    Q.push(start);
    while(!Q.empty()){
        int v=Q.front(), to;
        Q.pop();
        while((to=seg.extract(v))!=-1) if(to!=start){
            dis[to]=dis[v]+1;
            Q.push(to);
        }
    }
    dis[start]=0;
}

int main(){
    scanf("%d", &n);
    forn(i, n) scanf("%d %d", &arr[i].F, &arr[i].S), order[i]=i;
    bfs(0, dl);
    bfs(n-1, dr);
    forn(i, 2*n) ans[i]=INF;
    sort(order, order+n, [](int a, int b){
        return dl[a]+dr[a]<dl[b]+dr[b];
    });
    forn(i, n){
        int ind=order[i];
        modify(ind, query(arr[ind].F - 1, arr[ind].S, ans, dl[ind]+dr[ind])+1, ans);
    }
    scanf("%d", &q);
    forn(i, q) scanf("%d", &x), printf("%d\n", ans[n+x-1]>=INF? - 1 : ans[n+x-1]);
}

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
passport.cpp:76:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     forn(i, n) scanf("%d %d", &arr[i].F, &arr[i].S), order[i]=i;
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
passport.cpp:88:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     forn(i, q) scanf("%d", &x), printf("%d\n", ans[n+x-1]>=INF? - 1 : ans[n+x-1]);
      |                ~~~~~^~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46