Submission #874631

#	Time	Username	Problem	Language	Result	Execution time	Memory
874631		prvocislo	Passport (JOI23_passport)	C++17	22 / 100	371 ms	44448 KiB

passport

// 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 / 6
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46