Submission #741220

#	Time	Username	Problem	Language	Result	Execution time	Memory
741220		Username4132	Passport (JOI23_passport)	C++14	6 / 100	214 ms	8164 KiB

passport

#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)

const int MAXN=200010, INF=1e7;
int n, x, q, le[MAXN], ri[MAXN], order[MAXN], tr[3][2*MAXN];

void modify(int p, int value, int* t){
    for(p+=n, t[p]=value; p>1; p>>=1) t[p>>1]=min(t[p], t[p^1]);
}

int query(int l, int r, int* t){
    int res=INF;
    for(l+=n, r+=n; l<r; l>>=1, r>>=1){
        if(l&1) res=min(res, t[l++]);
        if(r&1) res=min(t[--r], res);
    }
    return res;
}

function<bool(int, int)> cmp[3]={
    [](int a, int b){return le[a]<le[b];},
    [](int a, int b){return ri[a]>ri[b];},
    [](int a, int b){return tr[0][n+a]+tr[1][n+a]<tr[0][n+b]+tr[1][n+b];}
};

function<int(int)> res[3]={
    [](int a){return le[a]==0? 0 : query(le[a], ri[a], tr[0])+1;},
    [](int a){return ri[a]==n? 0 : query(le[a], ri[a], tr[1])+1;},
    [](int a){return min(tr[0][n+a]+tr[1][n+a], query(le[a], ri[a], tr[2])+1);}
};

int main(){
    scanf("%d", &n);
    forn(i, n) scanf("%d %d", le+i, ri+i), --le[i], order[i]=i;
    forn(i, 3){
        forn(j, 2*n) tr[i][j]=INF;
        sort(order, order+n, cmp[i]);
        forn(j, n){
            int ind=order[j];
            modify(ind, res[i](ind), tr[i]);
        }
    }
    scanf("%d", &q);
    forn(i, q) scanf("%d", &x), printf("%d\n", tr[2][n+x-1]>=INF? -1 : tr[2][n+x-1]+1);
}

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
passport.cpp:37:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     forn(i, n) scanf("%d %d", le+i, ri+i), --le[i], order[i]=i;
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~
passport.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
passport.cpp:47:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     forn(i, q) scanf("%d", &x), printf("%d\n", tr[2][n+x-1]>=INF? -1 : tr[2][n+x-1]+1);
      |                ~~~~~^~~~~~~~~~

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