oj.uz

Submission #1085898

# Submission time Handle Problem Language Result Execution time Memory
1085898 2024-09-09T02:55:17 Z Bananabread Passport (JOI23_passport) C++17
48 / 100
 760 ms 455668 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();
        }
    }
}
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 91 ms 196180 KB Output is correct
2 Correct 75 ms 196156 KB Output is correct
3 Correct 76 ms 196180 KB Output is correct
4 Incorrect 85 ms 154884 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 75 ms 196176 KB Output is correct
2 Correct 85 ms 196160 KB Output is correct
3 Correct 97 ms 196240 KB Output is correct
4 Correct 75 ms 196180 KB Output is correct
5 Correct 77 ms 196180 KB Output is correct
6 Correct 76 ms 196176 KB Output is correct
7 Correct 81 ms 196244 KB Output is correct
8 Correct 81 ms 196300 KB Output is correct
9 Correct 78 ms 196176 KB Output is correct
10 Correct 76 ms 196344 KB Output is correct
11 Correct 87 ms 200784 KB Output is correct
12 Correct 84 ms 200816 KB Output is correct
13 Correct 82 ms 201044 KB Output is correct
14 Correct 84 ms 201044 KB Output is correct
15 Correct 96 ms 200784 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 196176 KB Output is correct
2 Correct 85 ms 196160 KB Output is correct
3 Correct 97 ms 196240 KB Output is correct
4 Correct 75 ms 196180 KB Output is correct
5 Correct 77 ms 196180 KB Output is correct
6 Correct 76 ms 196176 KB Output is correct
7 Correct 81 ms 196244 KB Output is correct
8 Correct 81 ms 196300 KB Output is correct
9 Correct 78 ms 196176 KB Output is correct
10 Correct 76 ms 196344 KB Output is correct
11 Correct 87 ms 200784 KB Output is correct
12 Correct 84 ms 200816 KB Output is correct
13 Correct 82 ms 201044 KB Output is correct
14 Correct 84 ms 201044 KB Output is correct
15 Correct 96 ms 200784 KB Output is correct
16 Correct 566 ms 427028 KB Output is correct
17 Correct 746 ms 448596 KB Output is correct
18 Correct 583 ms 438640 KB Output is correct
19 Correct 519 ms 433468 KB Output is correct
20 Correct 564 ms 425508 KB Output is correct
21 Correct 525 ms 451520 KB Output is correct
22 Correct 453 ms 436224 KB Output is correct
23 Correct 607 ms 455668 KB Output is correct
24 Correct 529 ms 450056 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 196176 KB Output is correct
2 Correct 85 ms 196160 KB Output is correct
3 Correct 97 ms 196240 KB Output is correct
4 Correct 75 ms 196180 KB Output is correct
5 Correct 77 ms 196180 KB Output is correct
6 Correct 76 ms 196176 KB Output is correct
7 Correct 81 ms 196244 KB Output is correct
8 Correct 81 ms 196300 KB Output is correct
9 Correct 78 ms 196176 KB Output is correct
10 Correct 76 ms 196344 KB Output is correct
11 Correct 87 ms 200784 KB Output is correct
12 Correct 84 ms 200816 KB Output is correct
13 Correct 82 ms 201044 KB Output is correct
14 Correct 84 ms 201044 KB Output is correct
15 Correct 96 ms 200784 KB Output is correct
16 Correct 566 ms 427028 KB Output is correct
17 Correct 746 ms 448596 KB Output is correct
18 Correct 583 ms 438640 KB Output is correct
19 Correct 519 ms 433468 KB Output is correct
20 Correct 564 ms 425508 KB Output is correct
21 Correct 525 ms 451520 KB Output is correct
22 Correct 453 ms 436224 KB Output is correct
23 Correct 607 ms 455668 KB Output is correct
24 Correct 529 ms 450056 KB Output is correct
25 Correct 77 ms 196272 KB Output is correct
26 Correct 75 ms 196256 KB Output is correct
27 Correct 576 ms 447548 KB Output is correct
28 Correct 760 ms 452272 KB Output is correct
29 Correct 561 ms 425552 KB Output is correct
30 Correct 538 ms 451408 KB Output is correct
31 Correct 520 ms 454740 KB Output is correct

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 196180 KB Output is correct
2 Correct 75 ms 196156 KB Output is correct
3 Correct 76 ms 196180 KB Output is correct
4 Incorrect 85 ms 154884 KB Output isn't correct
5 Halted 0 ms 0 KB -