oj.uz

Submission #1085899

# Submission time Handle Problem Language Result Execution time Memory
1085899 2024-09-09T02:55:58 Z Bananabread Passport (JOI23_passport) C++17
48 / 100
 762 ms 455688 KB 
#include<bits/stdc++.h>
#define ll long long
#define ntr "\n"
#define mod (ll)(1e9+7)
#define taskname "temp"
#define frep freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout);
using namespace std;
vector<array<int,3>> adj[2501][2501];
ll dist[2501][2501];
ll vis[2501][2501];
ll n,q;
ll l[200001];
ll r[200001];
void sub1(){
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
    }
    ll mx=r[1];
    ll ans=1;
    priority_queue<ll> q;
    for(int i=1;i<=mx;i++){
        if(i>mx){
            cout<<-1;
            return;
        }
        q.push(r[i]);
        if(i==mx){
            ans++;
            mx=q.top();
        }
    }
    cout<<ans;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //frep;
    cin>>n;
    if(n>2500){
        sub1();
        return 0;
    }
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
    }
    for(int i=1;i<=n;i++){
        ll mx=0,mn=1e18;
        adj[l[i]][r[i]].push_back({i,i,1});
        for(int j=i;j<=n;j++){
            mx=max(mx,r[j]);
            mn=min(mn,l[j]);
            if(i!=j){
                adj[i][mx].push_back({i,j,1});
                adj[mn][j].push_back({i,j,1});
                adj[i+1][j].push_back({i,j,0});
                adj[i][j-1].push_back({i,j,0});
            }
        }
    }
    memset(dist,0x3f,sizeof(dist));
    dist[1][n]=0;
    deque<array<ll,2>> dq;
    dq.push_front({1,n});
    while(!dq.empty()){
        ll u=dq.front()[0],v=dq.front()[1];
        dq.pop_front();
        if(vis[u][v]) continue;
        vis[u][v]=1;
        for(auto i:adj[u][v]){
            ll x=i[0],y=i[1],w=i[2];
            if(dist[x][y]>dist[u][v]+w){
                dist[x][y]=dist[u][v]+w;
                if(w==0){
                    dq.push_front({x,y});
                }
                else{
                    dq.push_back({x,y});
                }
            }
        }
    }
    cin>>q;
    for(int i=1;i<=q;i++){
        ll x;
        cin>>x;
        cout<<(dist[x][x] >= 1e18 ? -1 : dist[x][x])<<ntr;
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 196180 KB Output is correct
2 Correct 76 ms 196212 KB Output is correct
3 Correct 76 ms 196260 KB Output is correct
4 Incorrect 88 ms 152528 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 196180 KB Output is correct
2 Correct 76 ms 196212 KB Output is correct
3 Correct 80 ms 196176 KB Output is correct
4 Correct 76 ms 196252 KB Output is correct
5 Correct 78 ms 196180 KB Output is correct
6 Correct 76 ms 196180 KB Output is correct
7 Correct 76 ms 196180 KB Output is correct
8 Correct 77 ms 196224 KB Output is correct
9 Correct 76 ms 196240 KB Output is correct
10 Correct 77 ms 196180 KB Output is correct
11 Correct 85 ms 200868 KB Output is correct
12 Correct 83 ms 200784 KB Output is correct
13 Correct 84 ms 201072 KB Output is correct
14 Correct 83 ms 201040 KB Output is correct
15 Correct 82 ms 200900 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 196180 KB Output is correct
2 Correct 76 ms 196212 KB Output is correct
3 Correct 80 ms 196176 KB Output is correct
4 Correct 76 ms 196252 KB Output is correct
5 Correct 78 ms 196180 KB Output is correct
6 Correct 76 ms 196180 KB Output is correct
7 Correct 76 ms 196180 KB Output is correct
8 Correct 77 ms 196224 KB Output is correct
9 Correct 76 ms 196240 KB Output is correct
10 Correct 77 ms 196180 KB Output is correct
11 Correct 85 ms 200868 KB Output is correct
12 Correct 83 ms 200784 KB Output is correct
13 Correct 84 ms 201072 KB Output is correct
14 Correct 83 ms 201040 KB Output is correct
15 Correct 82 ms 200900 KB Output is correct
16 Correct 531 ms 426996 KB Output is correct
17 Correct 740 ms 448584 KB Output is correct
18 Correct 585 ms 438648 KB Output is correct
19 Correct 534 ms 433468 KB Output is correct
20 Correct 581 ms 425556 KB Output is correct
21 Correct 534 ms 451412 KB Output is correct
22 Correct 447 ms 436348 KB Output is correct
23 Correct 613 ms 455688 KB Output is correct
24 Correct 531 ms 449796 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 196180 KB Output is correct
2 Correct 76 ms 196212 KB Output is correct
3 Correct 80 ms 196176 KB Output is correct
4 Correct 76 ms 196252 KB Output is correct
5 Correct 78 ms 196180 KB Output is correct
6 Correct 76 ms 196180 KB Output is correct
7 Correct 76 ms 196180 KB Output is correct
8 Correct 77 ms 196224 KB Output is correct
9 Correct 76 ms 196240 KB Output is correct
10 Correct 77 ms 196180 KB Output is correct
11 Correct 85 ms 200868 KB Output is correct
12 Correct 83 ms 200784 KB Output is correct
13 Correct 84 ms 201072 KB Output is correct
14 Correct 83 ms 201040 KB Output is correct
15 Correct 82 ms 200900 KB Output is correct
16 Correct 531 ms 426996 KB Output is correct
17 Correct 740 ms 448584 KB Output is correct
18 Correct 585 ms 438648 KB Output is correct
19 Correct 534 ms 433468 KB Output is correct
20 Correct 581 ms 425556 KB Output is correct
21 Correct 534 ms 451412 KB Output is correct
22 Correct 447 ms 436348 KB Output is correct
23 Correct 613 ms 455688 KB Output is correct
24 Correct 531 ms 449796 KB Output is correct
25 Correct 77 ms 196180 KB Output is correct
26 Correct 85 ms 196128 KB Output is correct
27 Correct 538 ms 447568 KB Output is correct
28 Correct 762 ms 452232 KB Output is correct
29 Correct 575 ms 425492 KB Output is correct
30 Correct 529 ms 451412 KB Output is correct
31 Correct 508 ms 454656 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 196180 KB Output is correct
2 Correct 76 ms 196212 KB Output is correct
3 Correct 76 ms 196260 KB Output is correct
4 Incorrect 88 ms 152528 KB Output isn't correct
5 Halted 0 ms 0 KB -