oj.uz

Submission #741304

# Submission time Handle Problem Language Result Execution time Memory
741304 2023-05-14T01:45:44 Z Username4132 Passport (JOI23_passport) C++14
100 / 100
 305 ms 22472 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 244 ms 19080 KB Output is correct
5 Correct 169 ms 18616 KB Output is correct
6 Correct 139 ms 20680 KB Output is correct
7 Correct 102 ms 16288 KB Output is correct
8 Correct 90 ms 14824 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 4 ms 4988 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 4 ms 4988 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 4 ms 5204 KB Output is correct
17 Correct 4 ms 5204 KB Output is correct
18 Correct 4 ms 5076 KB Output is correct
19 Correct 5 ms 5204 KB Output is correct
20 Correct 5 ms 5164 KB Output is correct
21 Correct 5 ms 5204 KB Output is correct
22 Correct 4 ms 5204 KB Output is correct
23 Correct 4 ms 5332 KB Output is correct
24 Correct 6 ms 5176 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 4 ms 4988 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 4 ms 5204 KB Output is correct
17 Correct 4 ms 5204 KB Output is correct
18 Correct 4 ms 5076 KB Output is correct
19 Correct 5 ms 5204 KB Output is correct
20 Correct 5 ms 5164 KB Output is correct
21 Correct 5 ms 5204 KB Output is correct
22 Correct 4 ms 5204 KB Output is correct
23 Correct 4 ms 5332 KB Output is correct
24 Correct 6 ms 5176 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 3 ms 4948 KB Output is correct
27 Correct 6 ms 5204 KB Output is correct
28 Correct 5 ms 5164 KB Output is correct
29 Correct 5 ms 5204 KB Output is correct
30 Correct 5 ms 5204 KB Output is correct
31 Correct 5 ms 5176 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 244 ms 19080 KB Output is correct
5 Correct 169 ms 18616 KB Output is correct
6 Correct 139 ms 20680 KB Output is correct
7 Correct 102 ms 16288 KB Output is correct
8 Correct 90 ms 14824 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Correct 4 ms 4988 KB Output is correct
23 Correct 3 ms 4948 KB Output is correct
24 Correct 4 ms 5204 KB Output is correct
25 Correct 4 ms 5204 KB Output is correct
26 Correct 4 ms 5076 KB Output is correct
27 Correct 5 ms 5204 KB Output is correct
28 Correct 5 ms 5164 KB Output is correct
29 Correct 5 ms 5204 KB Output is correct
30 Correct 4 ms 5204 KB Output is correct
31 Correct 4 ms 5332 KB Output is correct
32 Correct 6 ms 5176 KB Output is correct
33 Correct 3 ms 4948 KB Output is correct
34 Correct 3 ms 4948 KB Output is correct
35 Correct 6 ms 5204 KB Output is correct
36 Correct 5 ms 5164 KB Output is correct
37 Correct 5 ms 5204 KB Output is correct
38 Correct 5 ms 5204 KB Output is correct
39 Correct 5 ms 5176 KB Output is correct
40 Correct 305 ms 20104 KB Output is correct
41 Correct 214 ms 20324 KB Output is correct
42 Correct 204 ms 19564 KB Output is correct
43 Correct 197 ms 19264 KB Output is correct
44 Correct 198 ms 22472 KB Output is correct
45 Correct 198 ms 21708 KB Output is correct
46 Correct 74 ms 10580 KB Output is correct
47 Correct 177 ms 19856 KB Output is correct
48 Correct 182 ms 20540 KB Output is correct