Submission #991012

#	Time	Username	Problem	Language	Result	Execution time	Memory
991012		Pacybwoah	Passport (JOI23_passport)	C++17	16 / 100	1841 ms	1048576 KiB

passport

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2")
#include<iostream>
#include<vector>
#include<utility>
#include<map>
using namespace std;
struct st{
    vector<int> vec;
    st(int n){
        vec.resize(4 * n + 4);
    }
    void build(int l, int r, int ind, vector<int>& sr){
        if(l == r){
            vec[ind] = sr[l];
        }
        else{
            int mid = (l + r) >> 1;
            build(l, mid, ind * 2, sr);
            build(mid + 1, r, ind * 2 + 1, sr);
            vec[ind] = min(vec[ind * 2], vec[ind * 2 + 1]);
        }
    }
    void modify(int l, int r, int num, int pos, int ind){
        if(l == r){
            vec[ind] = num;
            return;
        }
        int mid = (l + r) >> 1;
        if(pos <= mid) modify(l, mid, num, pos, ind * 2);
        else modify(mid + 1, r, num, pos, ind * 2 + 1);
        vec[ind] = min(vec[ind * 2], vec[ind * 2 + 1]);
    }
    int query(int l, int r, int start, int end, int ind){
        if(r < start || end < l) return 1e9;
        if(start <= l && r <= end) return vec[ind];
        int mid = (l + r) >> 1;
        return min(query(l, mid, start, end, ind * 2), query(mid + 1, r, start, end, ind * 2 + 1));
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<pair<int, int>> vec(n + 1);
    for(int i = 1; i <= n; i++) cin >> vec[i].first >> vec[i].second;
    map<pair<int, int>, vector<int>> m;
    for(int i = 1; i <= n; i++){
        m[vec[i]].push_back(i);
    }
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 1e9));
    dp[1][n] = 0;
    st mindp(n);
    vector<int> tmp(n + 1);
    vector<vector<int>> minl(n + 1, vector<int>(n + 1)), maxr(n + 1, vector<int>(n + 1));
    for(int i = 1; i <= n; i++) minl[i][i] = vec[i].first, maxr[i][i] = vec[i].second;
    for(int i = 1; i <= n; i++) for(int j = i + 1; j <= n; j++) minl[i][j] = min(minl[i][j - 1], vec[j].first), maxr[i][j] = max(maxr[i][j - 1], vec[j].second);
    for(int i = 1; i <= n; i++) tmp[i] = 1e9;
    mindp.build(1, n, 1, tmp);
    for(auto x: m[make_pair(1, n)]){
        mindp.modify(1, n, dp[1][n], x, 1);
    }
    for(int l = n - 1; l > 0; l--){
        for(int i = 1; i + l - 1 <= n; i++){
            int j = i + l - 1;
            if(n <= 300) dp[i][j] = min(dp[i][j], dp[minl[i][j]][j] + 1);
            if(n <= 300) dp[i][j] = min(dp[i][j], dp[i][maxr[i][j]] + 1);
            dp[i][j] = min(dp[i][j], mindp.query(1, n, i, j, 1) + 1);
            for(auto x: m[make_pair(i, j)]){
                mindp.modify(1, n, dp[i][j], x, 1);
            }
        }
    }
    int q;
    cin >> q;
    while(q--){
        int a;
        cin >> a;
        if(dp[a][a] == 1e9) cout << "-1\n";
        else cout << dp[a][a] << "\n";
    }
}
// g++ -std=gnu++20 pC.cpp -o run -Wall -Wextra -fsanitize=undefined -fsanitize=address

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