oj.uz

Submission #1085900

# Submission time Handle Problem Language Result Execution time Memory
1085900 2024-09-09T02:57:23 Z Bananabread Passport (JOI23_passport) C++17
48 / 100
 820 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<=n;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 88 ms 196184 KB Output is correct
2 Correct 84 ms 196220 KB Output is correct
3 Correct 86 ms 196180 KB Output is correct
4 Incorrect 92 ms 154828 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 85 ms 196176 KB Output is correct
2 Correct 84 ms 196180 KB Output is correct
3 Correct 83 ms 196260 KB Output is correct
4 Correct 84 ms 196180 KB Output is correct
5 Correct 93 ms 196320 KB Output is correct
6 Correct 82 ms 196092 KB Output is correct
7 Correct 93 ms 196168 KB Output is correct
8 Correct 85 ms 196180 KB Output is correct
9 Correct 84 ms 196128 KB Output is correct
10 Correct 80 ms 196180 KB Output is correct
11 Correct 98 ms 200964 KB Output is correct
12 Correct 100 ms 200764 KB Output is correct
13 Correct 89 ms 201040 KB Output is correct
14 Correct 95 ms 200892 KB Output is correct
15 Correct 101 ms 200884 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 196176 KB Output is correct
2 Correct 84 ms 196180 KB Output is correct
3 Correct 83 ms 196260 KB Output is correct
4 Correct 84 ms 196180 KB Output is correct
5 Correct 93 ms 196320 KB Output is correct
6 Correct 82 ms 196092 KB Output is correct
7 Correct 93 ms 196168 KB Output is correct
8 Correct 85 ms 196180 KB Output is correct
9 Correct 84 ms 196128 KB Output is correct
10 Correct 80 ms 196180 KB Output is correct
11 Correct 98 ms 200964 KB Output is correct
12 Correct 100 ms 200764 KB Output is correct
13 Correct 89 ms 201040 KB Output is correct
14 Correct 95 ms 200892 KB Output is correct
15 Correct 101 ms 200884 KB Output is correct
16 Correct 578 ms 427092 KB Output is correct
17 Correct 820 ms 448748 KB Output is correct
18 Correct 633 ms 438672 KB Output is correct
19 Correct 576 ms 433464 KB Output is correct
20 Correct 617 ms 425556 KB Output is correct
21 Correct 573 ms 451408 KB Output is correct
22 Correct 498 ms 436136 KB Output is correct
23 Correct 652 ms 455688 KB Output is correct
24 Correct 574 ms 449792 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 196176 KB Output is correct
2 Correct 84 ms 196180 KB Output is correct
3 Correct 83 ms 196260 KB Output is correct
4 Correct 84 ms 196180 KB Output is correct
5 Correct 93 ms 196320 KB Output is correct
6 Correct 82 ms 196092 KB Output is correct
7 Correct 93 ms 196168 KB Output is correct
8 Correct 85 ms 196180 KB Output is correct
9 Correct 84 ms 196128 KB Output is correct
10 Correct 80 ms 196180 KB Output is correct
11 Correct 98 ms 200964 KB Output is correct
12 Correct 100 ms 200764 KB Output is correct
13 Correct 89 ms 201040 KB Output is correct
14 Correct 95 ms 200892 KB Output is correct
15 Correct 101 ms 200884 KB Output is correct
16 Correct 578 ms 427092 KB Output is correct
17 Correct 820 ms 448748 KB Output is correct
18 Correct 633 ms 438672 KB Output is correct
19 Correct 576 ms 433464 KB Output is correct
20 Correct 617 ms 425556 KB Output is correct
21 Correct 573 ms 451408 KB Output is correct
22 Correct 498 ms 436136 KB Output is correct
23 Correct 652 ms 455688 KB Output is correct
24 Correct 574 ms 449792 KB Output is correct
25 Correct 84 ms 196176 KB Output is correct
26 Correct 79 ms 196176 KB Output is correct
27 Correct 544 ms 447568 KB Output is correct
28 Correct 813 ms 452148 KB Output is correct
29 Correct 643 ms 425660 KB Output is correct
30 Correct 579 ms 451408 KB Output is correct
31 Correct 555 ms 454744 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 196184 KB Output is correct
2 Correct 84 ms 196220 KB Output is correct
3 Correct 86 ms 196180 KB Output is correct
4 Incorrect 92 ms 154828 KB Output isn't correct
5 Halted 0 ms 0 KB -