oj.uz

Submission #991964

# Submission time Handle Problem Language Result Execution time Memory
991964 2024-06-03T13:04:50 Z onbert Passport (JOI23_passport) C++17
46 / 100
 330 ms 41044 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 20, m = 450, INF = 1e9;
int Rcost[maxn];
pair<int,int> Lcost[maxn];
bool cmp(int a, int b) {
    return Lcost[a].second < Lcost[b].second;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    pair<int,int> a[n+1];
    vector<pair<int,int>> Lpos[m], Rpos[m];
    vector<pair<int,int>> lpos[n+1], rpos[n+1];
    for (int i=1;i<=n;i++) {
        cin >> a[i].first >> a[i].second;
        if (i!=1) {
            Lpos[a[i].first/m].push_back({a[i].second, i});
            lpos[a[i].first].push_back({a[i].second, i});
        }
        if (i!=n) {
            Rpos[a[i].second/m].push_back({a[i].first, i});
            rpos[a[i].second].push_back({a[i].first, i});
        }
    }


    for (int i=0;i<m;i++) sort(Rpos[i].rbegin(), Rpos[i].rend());
    for (int i=1;i<=n;i++) sort(rpos[i].rbegin(), rpos[i].rend());
    bool vis[n+1];
    for (int i=1;i<=n;i++) vis[i] = false;
    vis[n] = true;
    vector<int> from = {n}, to;
    int Rcost[n+1];
    for (int i=1;i<=n;i++) Rcost[i] = INF;
    for (int cost=-1; from.size()>0; cost++) {
        for (int u:from) Rcost[u] = max(cost, (int)0);
        for (int u:from) {
            for (int R=m-1;R*m>=u;R--) {
                while (Rpos[R].size()>0 && Rpos[R].back().first<=u) {
                    int v = Rpos[R].back().second;
                    if (!vis[v]) to.push_back(v);
                    vis[v] = true;
                    Rpos[R].pop_back();
                }
            }
            int r = min((u+m-1)/m*m - 1, n);
            for (;r>=u;r--) {
                    while (rpos[r].size()>0 && rpos[r].back().first<=u) {
                    int v = rpos[r].back().second;
                    if (!vis[v]) to.push_back(v);
                    vis[v] = true;
                    rpos[r].pop_back();
                }
            }
        }
        from.clear();
        swap(to, from);
    }

    for (int i=0;i<m;i++) sort(Lpos[i].begin(), Lpos[i].end());
    for (int i=0;i<=n;i++) sort(lpos[i].begin(), lpos[i].end());
    for (int i=1;i<=n;i++) vis[i] = false;
    vis[1] = true;
    from = {1};
    for (int i=1;i<=n;i++) Lcost[i] = {INF, INF};
    Lcost[1].second = Rcost[1] + 1;
    for (int cost=0; from.size()>0; cost++) {
        sort(from.begin(), from.end(), cmp);
        for (int u:from) Lcost[u].first = cost;
        for (int u:from) {
            for (int L=0;(L+1)*m-1<=u;L++) {
                while (Lpos[L].size()>0 && Lpos[L].back().first>=u) {
                    int v = Lpos[L].back().second;
                    if (!vis[v]) {
                        to.push_back(v);
                        Lcost[v].second = min(Rcost[v], Lcost[u].second);
                    }
                    vis[v] = true;
                    Lpos[L].pop_back();
                }
            }
            int l = u/m*m;
            for (;l<=u;l++) {
                    while (lpos[l].size()>0 && lpos[l].back().first>=u) {
                    int v = lpos[l].back().second;
                    if (!vis[v]) {
                        to.push_back(v);
                        Lcost[v].second = min(Rcost[v], Lcost[u].second);
                    }
                    vis[v] = true;
                    lpos[l].pop_back();
                }
            }
        }
        from.clear();
        swap(to, from);
    }
    
    int q;
    cin >> q;
    for (int i=0;i<q;i++) {
        int pos;
        cin >> pos;
        if (Lcost[pos].first>=INF || Lcost[pos].second>=INF) cout << "-1\n";
        else cout << Lcost[pos].first + Lcost[pos].second << "\n";
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 330 ms 38648 KB Output is correct
5 Correct 290 ms 38828 KB Output is correct
6 Correct 282 ms 41044 KB Output is correct
7 Correct 214 ms 38512 KB Output is correct
8 Correct 96 ms 30736 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 392 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 3 ms 916 KB Output is correct
18 Correct 3 ms 940 KB Output is correct
19 Correct 3 ms 856 KB Output is correct
20 Correct 3 ms 860 KB Output is correct
21 Correct 3 ms 856 KB Output is correct
22 Correct 2 ms 860 KB Output is correct
23 Correct 4 ms 860 KB Output is correct
24 Correct 2 ms 916 KB Output is correct

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 392 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 3 ms 916 KB Output is correct
18 Correct 3 ms 940 KB Output is correct
19 Correct 3 ms 856 KB Output is correct
20 Correct 3 ms 860 KB Output is correct
21 Correct 3 ms 856 KB Output is correct
22 Correct 2 ms 860 KB Output is correct
23 Correct 4 ms 860 KB Output is correct
24 Correct 2 ms 916 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Incorrect 3 ms 860 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 330 ms 38648 KB Output is correct
5 Correct 290 ms 38828 KB Output is correct
6 Correct 282 ms 41044 KB Output is correct
7 Correct 214 ms 38512 KB Output is correct
8 Correct 96 ms 30736 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 392 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 3 ms 860 KB Output is correct
25 Correct 3 ms 916 KB Output is correct
26 Correct 3 ms 940 KB Output is correct
27 Correct 3 ms 856 KB Output is correct
28 Correct 3 ms 860 KB Output is correct
29 Correct 3 ms 856 KB Output is correct
30 Correct 2 ms 860 KB Output is correct
31 Correct 4 ms 860 KB Output is correct
32 Correct 2 ms 916 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Incorrect 3 ms 860 KB Output isn't correct
36 Halted 0 ms 0 KB -