Submission #1178813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178813		1231231231	Passport (JOI23_passport)	C++20	6 / 100	1797 ms	109196 KiB

passport

#pragma GCC optimize "Ofast"

///In honor of TimDee

/*
In honor of Anton Tsypko
I want earrings with minecreaft
I want earrings with birbie
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <string>
#include <queue>
#include <random>
#include <chrono>
#include <unordered_map>
#include <stack>


using namespace std;


//#define int long long

int inf = 1000000000;
int mod = 1000000007;
int log_ = 18;

struct segment_tree {
    vector <int> mn;
    vector <int> mx;


    int s = 0;

    void init(int n) {
        s = 1;

        while (s < n)
            s *= 2;

        mn.resize(2 * s);
        mx.resize(2 * s);
    }

    void modif(int ind, int l, int r, int indx, int x, int y) {
        if (r - l == 1) {
            mn[ind] = x;
            mx[ind] = y;

            return;
        }

        int m = (l + r) / 2;

        if (indx < m)
            modif(ind * 2 + 1, l, m, indx, x, y);
        else
            modif(ind * 2 + 2, m, r, indx, x, y);

        mn[ind] = min(mn[ind * 2 + 1], mn[ind * 2 + 2]);
        mx[ind] = max(mx[ind * 2 + 1], mx[ind * 2 + 2]);
    }

    void modif(int indx, int x, int y) {
        return modif(0, 0, s, indx, x, y);
    }


    void modif2(int ind, int l, int r, int indx, int x) {
        if (r - l == 1) {
            mn[ind] = min(mn[ind] , x);
            
            return;
        }

        int m = (l + r) / 2;

        if (indx < m)
            modif2(ind * 2 + 1, l, m, indx, x);
        else
            modif2(ind * 2 + 2, m, r, indx, x);

        mn[ind] = min(mn[ind * 2 + 1], mn[ind * 2 + 2]);
    }

    void modif2(int indx, int x) {
        return modif2(0, 0, s, indx, x);
    }



    int get_mn(int ind, int l, int r, int lx, int rx) {
        if ((lx <= l) and (r <= rx)) {
            return mn[ind];
        }

        if ((r <= lx) or (rx <= l))
            return inf;

        int m = (l + r) / 2;

        int g1 = get_mn(ind * 2 + 1, l, m, lx, rx);
        int g2 = get_mn(ind * 2 + 2, m, r, lx, rx);


        return min(g1, g2);
    }


    int get_mn(int l, int r) {
        return get_mn(0, 0, s, l, r);
    }






    int get_mx(int ind, int l, int r, int lx, int rx) {
        if ((lx <= l) and (r <= rx)) {
            return mx[ind];
        }

        if ((r <= lx) or (rx <= l))
            return -inf;

        int m = (l + r) / 2;

        int g1 = get_mx(ind * 2 + 1, l, m, lx, rx);
        int g2 = get_mx(ind * 2 + 2, m, r, lx, rx);


        return max(g1, g2);
    }


    int get_mx(int l, int r) {
        return get_mx(0, 0, s, l, r);
    }
};

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);

    int n;
    cin >> n;

    vector <int> l(n);
    vector <int> r(n);

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

        l[i]--;
        r[i]--;
    }

    vector <vector <pair <int, int>>> bin(log_);
    vector <segment_tree> st(log_);

    for (int i = 0; i < log_; i++) {
        st[i].init(n);
        bin[i].resize(n);
    }

    for (int i = 0; i < n; i++) {
        bin[0][i].first = l[i];
        bin[0][i].second = r[i];

        st[0].modif(i, l[i], r[i]);
    }

    for (int j = 1; j < log_; j++) {
        for (int i = 0; i < n; i++) {
            int l_ = bin[j - 1][i].first;
            int r_ = bin[j - 1][i].second;

            bin[j][i].first = st[j - 1].get_mn(l_, r_ + 1);
            bin[j][i].second = st[j - 1].get_mx(l_, r_ + 1);

            st[j].modif(i, bin[j][i].first, bin[j][i].second);
        }
    }

    int mx_ = n - 1;

    for (int i = n - 1; i >= 0; i--) {
        if (r[i] == n - 1)
            mx_ = i;
    }

    int mn_ = 0;

    for (int i = 0; i < n; i++) {
        if (l[i] == 0)
            mn_ = i;
    }

    vector <int> ans(n);

    for (int i = 0; i < n; i++) {
        if ((l[i] == 0) and (r[i] == n - 1))
        {
            ans[i] = 1;
            continue;
        }

        if (l[i] == 0) {
            if (r[i] == 0)
            {
                ans[i] = inf;
                continue;
            }

            int r_ = r[i];
            int col = 2;

            for (int j = log_ - 1; j >= 0; j--) {
                int r__ = st[j].get_mx(0, r_ + 1);

                if (r__ < mx_) {
                    col += (1 << j);
                    r_ = r__;
                }
            }
            
            if (r_ < mx_)
            {
                int r__ = st[0].get_mx(0, r_ + 1);

                if (r__ >= mx_) {
                    col++;
                }
                else
                {
                    ans[i] = inf;
                    continue;
                }
            }

            if (col > 2 * n)
            {
                ans[i] = inf;
                continue;
            }


            ans[i] = col;

            continue;
        }


        if (r[i] == n - 1) {
            if (l[i] == n - 1)
            {
                ans[i] = inf;
                continue;
            }

            int l_ = l[i];
            int col = 2;

            for (int j = log_ - 1; j >= 0; j--) {
                int l__ = st[j].get_mn(l_, n);

                if (l__ > mn_) {
                    col += (1 << j);
                    l_ = l__;
                }
            }

            if (l_ > mn_)
            {
                int l__ = st[0].get_mn(l_, n);

                if (l__ <= mn_) {
                    col++;
                    l_ = l__;
                }
                else
                {
                    ans[i] = inf;
                    continue;
                }
            }

            if (col > 2 * n)
            {
                ans[i] = inf;
                continue;
            }

            ans[i] = col;

            continue;
        }

        ans[i] = inf;
    }

    /*
        for (int i = 0 ; i <n ; i++)
            cout << ans[i] << " ";
    */

    segment_tree ans_;

    ans_.init(n);

    for (int i = 0; i < n; i++) {
        ans_.modif(i, ans[i], ans[i]);
    }

    for (int j = 0; j < log_; j++) {
        for (int i = 0; i < n; i++) {
            int g = ans_.get_mn(bin[j][i].first, bin[j][i].second + 1);
            
            ans_.modif2(i, g + (1 << j));
        }
    }

    int q;
    cin >> q;


    for (int i = 0; i < q; i++) {
        int ind;
        cin >> ind;


        ind--;

        int g = ans_.get_mn(ind, ind + 1);

        if (g == inf)
            cout << -1 << "\n";
        else
            cout << g << "\n";
    }

}

/*
000
30
3310
331110
333110
332110
33222110
33322110
33222110
33322110
33222110
*/

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