oj.uz

Submission #874631

# Submission time Handle Problem Language Result Execution time Memory
874631 2023-11-17T12:44:22 Z prvocislo Passport (JOI23_passport) C++17
22 / 100
 371 ms 44448 KB 
// Just by leaving I’m helping them another day

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

const int inf = 1e9 + 5;
struct sgttree // hlada maximum
{
    int n;
    vector<pair<int, int> > st;
    void init(int N, vector<int> a)
    {
        n = N;
        st.assign(2 * n, { -inf, -1 });
        for (int i = n; i < 2 * n; i++) st[i] = { a[i - n], i - n };
        for (int i = n - 1; i >= 0; i--) st[i] = max(st[(i << 1)], st[(i << 1) + 1]);
    }
    pair<int, int> query(int l, int r)
    {
        pair<int, int> p(-inf, -1);
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
        {
            if (l & 1) p = max(p, st[l++]);
            if (r & 1) p = max(p, st[--r]);
        }
        return p;
    }
};
void bfs(int n, vector<int>& d, vector<vector<int> >& g) // vzdialenost inf ak sa niekam nevieme dostat
{
    set<pair<int, int> > pq;
    for (int i = 0; i < n; i++) pq.insert({ d[i], i });
    while (!pq.empty())
    {
        int u = pq.begin()->second;
        pq.erase(pq.begin());
        for (int v : g[u]) if (d[u] + 1 < d[v])
        {
            pq.erase({ d[v], v });
            d[v] = d[u] + 1;
            pq.insert({ d[v], v });
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> l(n), r(n);
    for (int i = 0; i < n; i++) cin >> l[i] >> r[i], l[i] = -(l[i] - 1), r[i]--;
    sgttree mi, mx;
    mi.init(n, r);
    mx.init(n, l);
    for (int i = 0; i < n; i++) l[i] = -l[i];
    vector<vector<int> > g(n), gr(n);
    vector<int> d0(n, inf), dn(n, inf);
    for (int i = 0; i < n; i++)
    {
        if (l[i] == 0) d0[i] = 0;
        if (r[i] == n - 1) dn[i] = 0;
    }
    for (int i = 0; i < n; i++)
    {
        int mij = mi.query(l[i], r[i]).second;
        int mxj = mx.query(l[i], r[i]).second;
        g[i].push_back(mij), g[i].push_back(mxj);
        gr[mij].push_back(i), gr[mxj].push_back(i);
    }
    bfs(n, d0, gr);
    bfs(n, dn, gr);
    vector<int> d(n, inf);
    for (int i = 0; i < n; i++) d[i] = min(inf, d0[i] + dn[i] + 1);
    bfs(n, d, gr);
    int q;
    cin >> q;
    while (q--)
    {
        int x;
        cin >> x;
        //cout << "                   ";
        x--;
        if (d[x] == inf) cout << "-1\n";
        else cout << d[x] << "\n";
    }
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 371 ms 39376 KB Output is correct
5 Correct 267 ms 41540 KB Output is correct
6 Correct 210 ms 44448 KB Output is correct
7 Correct 156 ms 37796 KB Output is correct
8 Correct 120 ms 30820 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 452 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 456 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 1 ms 348 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 452 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 456 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 1 ms 348 KB Output is correct
16 Correct 3 ms 924 KB Output is correct
17 Incorrect 4 ms 860 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 456 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 452 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 456 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 1 ms 348 KB Output is correct
16 Correct 3 ms 924 KB Output is correct
17 Incorrect 4 ms 860 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 371 ms 39376 KB Output is correct
5 Correct 267 ms 41540 KB Output is correct
6 Correct 210 ms 44448 KB Output is correct
7 Correct 156 ms 37796 KB Output is correct
8 Correct 120 ms 30820 KB Output is correct
9 Correct 1 ms 456 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 456 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 452 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 456 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 1 ms 348 KB Output is correct
24 Correct 3 ms 924 KB Output is correct
25 Incorrect 4 ms 860 KB Output isn't correct
26 Halted 0 ms 0 KB -