oj.uz

Submission #741220

# Submission time Handle Problem Language Result Execution time Memory
741220 2023-05-13T21:23:29 Z Username4132 Passport (JOI23_passport) C++14
6 / 100
 214 ms 8164 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 214 ms 8088 KB Output is correct
5 Correct 123 ms 8096 KB Output is correct
6 Correct 94 ms 8164 KB Output is correct
7 Correct 79 ms 7756 KB Output is correct
8 Correct 80 ms 6340 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 214 ms 8088 KB Output is correct
5 Correct 123 ms 8096 KB Output is correct
6 Correct 94 ms 8164 KB Output is correct
7 Correct 79 ms 7756 KB Output is correct
8 Correct 80 ms 6340 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Incorrect 1 ms 340 KB Output isn't correct
23 Halted 0 ms 0 KB -