Submission #767749

#	Time	Username	Problem	Language	Result	Execution time	Memory
767749		dimash241	Passport (JOI23_passport)	C++17	100 / 100	868 ms	78328 KiB

passport

#include <cstdio>
#include <random>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <chrono>


#define ll long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;

// вправо, вниз, влево, вверх
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

// ход конем
//int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
//int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
mt19937_64 rnd64(chrono::system_clock::now().time_since_epoch().count());
int rndInteger (int l, int r) {
    return uniform_int_distribution<int> (l, r)(rnd);
}

const int MOD = (int) 998244353;
const int N = (int) 3e5 + 7;

int n, q;
int l[N], r[N];

int d[4][N];

int vis[N * 4];

vector<int> g, t[N * 4];

void upd(int l, int r, int id, int v = 1, int tl = 1, int tr = n) {
    if(tr < l || r < tl || vis[v]) return;
    if(tl >= l && tr <= r) {
        t[v].push_back(id);
        return;
    }
    int tm = (tl+tr)>>1;
    upd(l, r, id, v<<1, tl, tm);
    upd(l, r, id, v<<1|1, tm+1, tr);
}

void get(int p, int v = 1, int tl = 1, int tr = n) {
    for (auto to : t[v])
        g.push_back(to);
    t[v].clear();

    if(tl == tr) return;

    int tm = (tl+tr) >> 1;
    if(p <= tm) {
        get(p, v<<1, tl, tm);
    } else {
        get(p, v<<1 | 1, tm + 1, tr);
    }
}

void init() {
    memset(vis, 0, sizeof vis);
    for (int v = 1; v <= n; ++v) {
        upd(l[v], r[v], v);
    }
}

void djk(int id, int st) {
    for (int v = 1; v <= n; ++v) {
        d[id][v] = 1e9;
    }

    d[id][st] = 0;
    set<pair<int,int>> s;
    s.insert({1, st});
    //cout << "start: " << st << endl;
    while(sz(s)) {
        int v = s.begin()->second;
        s.erase(s.begin());

        get(v);

        for (int to : g) {
            if(d[id][to] > d[id][v] + 1) {
                s.erase({d[id][to], to});
                d[id][to] = d[id][v] + 1;
                s.insert({d[id][to], to});
            }
        }
        g.clear();
    }
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> l[i] >> r[i];
    }

    init();
    djk(0, 1);


    init();
    djk(1, n);

    init();
    set<pair<int,int>> s;
    for (int v = 1; v <= n; ++v) {
//        cout << "here: " << v << ' ' << d[0][v] << ' ' << d[1][v] << '\n';
       if(v == 1) {
            d[2][v] = d[1][v];
        } else if(v == n) {
            d[2][v] = d[0][v];
        } else {
            d[2][v] = d[1][v] + d[0][v] - 1;
        }

        if(d[2][v] < 1e9) {
            s.insert({d[2][v], v});
        }
    }

    while(sz(s)) {
        while(sz(s)) {
            int v = s.begin()->second;
            s.erase(s.begin());

            get(v);

            for (int to : g) {
                if(d[2][to] > d[2][v] + 1) {
                    s.erase({d[2][to], to});
                    d[2][to] = d[2][v] + 1;
                    s.insert({d[2][to], to});
                }
            }
            g.clear();
        }
    }

    cin >> q;
    for(; q; --q) {
        int x;
        cin >> x;
        int res = d[2][x];
        if(res >= 1e9) res = -1;
        cout << res << '\n';
    }




    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46