Submission #803089

#	Time	Username	Problem	Language	Result	Execution time	Memory
803089		lukameladze	Passport (JOI23_passport)	C++17	48 / 100	335 ms	63236 KiB

passport

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int,int>
#define pb push_back
const int N = 1e5 + 5;
int n, l[N], r[N];
pii tree[4 * N];
multiset <pii> ms[4 * N];
void update(int node, int le, int ri, int idx, int val, int id) {
    if (le > idx || ri < idx) return ;
    if (le == ri) {
        // cout<<"upd "<<le<<" "<<ri<<" "<<node<<"\n";
        if (val == 0) {
            if (!ms[node].size()) {
                // cout<<node<<" "<<idx<<" "<<val<<" "<<id<<"\n";
                // exit(0);
                assert(false);
            }
            assert(ms[node].size());
            ms[node].erase(--ms[node].end());
            if (!ms[node].size()) {
                tree[node] = {0, 0}; return ;
            }
        } 
        if (val != 0) ms[node].insert({val, id});
        auto it = --ms[node].end();
        tree[node] = {(*it).f, (*it).s};
        return ;
    }
    int mid = (le + ri) / 2;
    update(2 * node, le, mid, idx, val, id);
    update(2 * node + 1, mid + 1, ri, idx, val, id);
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}
pii getans(int node, int le, int ri, int start, int end) {
    if (le > end || ri < start) return {0, 0};
    if (le >= start && ri <= end) return tree[node];
    int mid = (le + ri) / 2;
    return max(getans(2 * node, le, mid, start, end), getans(2 * node + 1, mid + 1, ri ,start, end));
}
int dp[2][N];
void bfs(int a, int ty) {
    for (int i = 0; i < 4 * N; i++) {
        tree[i] = {0, 0}; 
        ms[i].clear();
    }
    for (int i = 1; i <= n; i++) {
        if (i == a) continue;
        dp[ty][i] = 1e9;
        update(1, 1, n, l[i], r[i], i);
    }
    
    queue <int> q;
    q.push(a);
    dp[ty][a] = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        while (getans(1, 1, n, 1, x).f >= x) {
            pii sth = getans(1, 1, n, 1, x);
            q.push(sth.s);
            dp[ty][sth.s] = dp[ty][x] + 1;
            update(1, 1, n, l[sth.s], 0, sth.s);
        }
    }
}

int tree_mn[4 * N];
void upd_mn(int node, int le, int ri, int idx, int val) {
    if (le > idx || ri < idx) return ;
    if (le == ri) {
        tree_mn[node] = val; return ;
    }
    int mid = (le + ri) / 2;
    upd_mn(2 * node, le, mid, idx,val);
    upd_mn(2 * node + 1, mid + 1, ri, idx,val);
    tree_mn[node] = min(tree_mn[2 * node], tree_mn[2 * node + 1]);
}
int get_mn(int node, int le, int ri, int start, int end) {
    if (le > end || ri < start) return 1e9;
    if (le >= start && ri <= end) return tree_mn[node];
    int mid = (le + ri) / 2;
    return min(get_mn(2 * node, le ,mid, start, end), get_mn(2 * node + 1, mid + 1, ri, start, end));
}
signed main() {
    std::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];
    }
    bfs(1, 0);
    bfs(n, 1);
    vector <pii> vec;
    for (int i = 1; i <= n; i++) {
        vec.pb({dp[0][i] + dp[1][i] - (i != 1 && i != n), i});
    }
    sort(vec.begin(), vec.end());
    for (pii sth : vec) {
        upd_mn(1, 1, n, sth.s, sth.f);
    }
    vector <int> res(n + 5, 0);
    for (int i = 0; i < (int)vec.size(); i++) {
        int id = vec[i].s;
        res[id] = min(vec[i].f, get_mn(1, 1, n, l[id], r[id]) + 1);
        upd_mn(1, 1, n, id, res[id]);
    }
    int q;
    cin>>q;
    while(q--) {
        int idx; cin>>idx;
        cout<<(res[idx] >= 1e9 ? -1 : res[idx])<<"\n";
    }
}

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