Submission #943485

#	Time	Username	Problem	Language	Result	Execution time	Memory
943485		vjudge1	Passport (JOI23_passport)	C++17	0 / 100	2 ms	8540 KiB

passport

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define db double
#define ll __int128
#define int long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;

const int Max = 1e5 + 7, Inf = 1e9 + 7;

void print(bool x) { cout << (x ? "YES" : "NO") << endl; }

string tostring (__int128 x)
{
    string ans = "";
    while(x > 0)
    {
        ans += (x % 10 + '0');
        x /= 10;
    }
    reverse(all(ans));
    return ans;
}

struct SegmentTree
{
    struct node
    {
        int l1, r1, l2, r2;

        node(int _l1 = Inf, int _r1 = 0, int _l2 = Inf, int _r2 = 0)
        {
            l1 = _l1; r1 = _r1;
            l2 = _l2; r2 = _r2; 
        }
    };

    vector <node> tree; int l;

    node merge(node a, node b)
    {
        return node(min(a.l1, b.l1), 
                    (a.l1 == b.l1 ? max(a.r1, b.r1) : (a.l1 < b.l1 ? a.r1 : b.r1)),
                    (a.r2 == b.r2 ? max(a.l2, b.l2) : (a.r2 > b.r2 ? a.l2 : b.l2)),
                    max(a.r2, b.r2));
    }

    void update(int k, int v1, int v2)
    {
        k += (l - 1); tree[k] = node(v1, v2, v1, v2);
        for(k /= 2; k > 0; k /= 2)
            tree[k] = merge(tree[2*k], tree[2*k+1]);
    }

    node query(int k, int x, int y, int s, int e)
    {
        if(s > y || e < x)
            return node();
        if(s >= x && e <= y)
            return tree[k];

        int middle = (s + e) / 2;

        return merge(query(2*k, x, y, s, middle),
            query(2*k+1, x, y, middle + 1, e));
    }

    pair <pair<int, int>, pair<int, int>> query(int x, int y)
    {
        node ans = query(1, x, y, 1, l);
        return { { ans.l1, ans.r1 }, { ans. l2, ans.r2 } };
    }

    SegmentTree(int n)
    {
        for(l = 1; l < n; (l <<= 1));
        tree.assign(2 * l, node());
    }
} St(Max);

map <int, map <int, int>> mp; int n; 

int dp(int l, int r)
{
    if(l == 1 && r == n) return 0;
    if(mp[l][r] != 0) return mp[l][r];
    mp[l][r] = Inf;
    pair <pair<int, int>, pair<int, int>> q = St.query(l, r);
    return mp[l][r] = min(dp(q.fs.fs, q.fs.sd), dp(q.sd.fs, q.sd.sd)) + 1;
}

void solve()
{
    cin >> n; vector <pair<int, int>> v(n);

    for(int i = 0; i < n; i++) 
    {
        cin >> v[i].fs >> v[i].sd;
        St.update(i + 1, v[i].fs, v[i].sd);
    }

    int q; cin >> q; 

    while(q--)
    {
        int x, ans; cin >> x; x--;
        ans = dp(v[x].fs, v[x].sd);
        cout << (ans >= Inf ? -1 : ans + 1) << endl;
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int Q = 1; //cin >> Q;

    while (Q--)
    {
        solve();
    }

    return 0;
}

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