Submission #1183236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183236		Gray	Passport (JOI23_passport)	C++20	22 / 100	276 ms	278968 KiB

passport

#ifndef LOCAL
// #pragma GCC optimize("O3,Ofast")
// #pragma GCC target("sse2")
#endif
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD (ll)(1e9+7)

ll n, q;
vector<pair<ll, ll>> ls, rs;
struct ST{
    vector<vector<pair<ll, ll>>> stMN, stMX;
    vector<ll> log; ll N;

    pair<ll, ll> mergeMN(pair<ll, ll> l, pair<ll, ll> r){
        if (l.ff==r.ff){
            if (rs[l.ss].ff>rs[r.ss].ff) return l;
            else return r;
        }else{
            if (l.ff>r.ff) return r;
            else return l;
        }
    }
    pair<ll, ll> mergeMX(pair<ll, ll> l, pair<ll, ll> r){
        if (l.ff==r.ff){
            if (ls[l.ss].ff<ls[r.ss].ff) return l;
            else return r;
        }else{
            if (l.ff>r.ff) return l;
            else return r;
        }
    }
    void init(ll _n, vector<pair<ll, ll>> &a){
        N=_n; log.resize(N+1);
        for (ll i=2; i<=N; i++) log[i]=log[i/2]+1;
        stMN.resize(log[N]+1, vector<pair<ll, ll>>(N));
        stMX.resize(log[N]+1, vector<pair<ll, ll>>(N));
        stMN[0]=stMX[0]=a;
        for (ll i=1; i<=log[N]; i++){
            for (ll j=0; j<(N-(1<<(i-1))); j++) {
                stMN[i][j]=mergeMN(stMN[i-1][j], stMN[i-1][j+(1<<(i-1))]);
                stMX[i][j]=mergeMX(stMX[i-1][j], stMX[i-1][j+(1<<(i-1))]);
            }
        }
    }

    pair<ll, ll> queryMN(ll l, ll r){
        ll lg = log[r-l+1];
        // for (auto ch:stMN[0]) cout << ch.ff << " ";
        pair<ll, ll> res = mergeMN(stMN[lg][l], stMN[lg][r-(1<<lg)+1]);
        // cout << " L -> " << res.ff << ln;
        return res;
    }
    pair<ll, ll> queryMX(ll l, ll r){
        ll lg = log[r-l+1];
        // for (auto ch:stMX[0]) cout << ch.ff << " ";
        pair<ll, ll> res=mergeMX(stMX[lg][l], stMX[lg][r-(1<<lg)+1]);
        // cout << " R " << l << "-" << r << " -> " << res.ff << ln;
        return res;
    }
};


vector<map<ll, ll>> dp;
ST mns, mxs;
ll rec(ll l, ll r){
    // cout << l << " - " << r << ln;
    if (l==0 and r==n-1){
        return 1;
    }else{
        if (!dp[l].count(r)){
            dp[l][r]=INF;
            ll mnl = mns.queryMN(l, r).ss;
            ll mxr = mxs.queryMX(l, r).ss;
            // cout << mnl << " & " << mxr << ln;
            if (ls[mnl].ff<l or rs[mnl].ff>r) dp[l][r] = min(dp[l][r], rec(min(l, ls[mnl].ff), max(r, rs[mnl].ff))+1);
            if (ls[mxr].ff<l or rs[mxr].ff>r) dp[l][r] = min(dp[l][r], rec(min(l, ls[mxr].ff), max(r, rs[mxr].ff))+1);
        }
        return dp[l][r];
    }
}

void gave_up(){
    cin >> n; vector<pair<ll, ll>> rng(n);
    ls.resize(n); rs.resize(n);
    dp.resize(n);
    for (ll i=0; i<n; i++){
        cin >> rng[i].ff >> rng[i].ss; rng[i].ff--; rng[i].ss--;
        ls[i]={rng[i].ff, i}; rs[i]={rng[i].ss, i};
    }
    mns.init(n, ls); mxs.init(n, rs);
    cin >> q;
    while (q--){
        ll x; cin >> x; x--;
        ll res=rec(rng[x].ff, rng[x].ss);
        cout << (res>=INF?-1:res) << ln;
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll t=1;
    // cin >> t;
    for (ll c=1; c<=t; c++) gave_up();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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