제출 #749210

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
749210		Lucpp	Passport (JOI23_passport)	C++17	100 / 100	1000 ms	78836 KiB

passport

#include <bits/stdc++.h>
using namespace std;
constexpr int inf = 1e8;
typedef pair<int, int> pi;

struct Seg{
    vector<pi> seg;
    int cap;
    Seg(vector<int> v){
        int n = (int)v.size();
        for(cap=1; cap<n; cap*=2);
        seg.assign(2*cap, {inf, inf});
        for(int i = 0; i < n; i++) seg[i+cap] = {v[i], i};
        for(int i = cap-1; i >= 1; i--) seg[i] = min(seg[2*i], seg[2*i+1]);
    }
    void upd(int i, int v){
        i += cap;
        seg[i].first = v;
        while(i > 1){
            i /= 2;
            seg[i] = min(seg[2*i], seg[2*i+1]);
        }
    }
    pi qry(int l, int r, int a, int b, int i){
        if(l <= a && b <= r) return seg[i];
        if(b < l || r < a) return {inf, inf};
        int m = (a+b)/2;
        return min(qry(l, r, a, m, 2*i), qry(l, r, m+1, b, 2*i+1));
    }
    pi qry(int l, int r){return qry(l+1, r+1, 1, cap, 1);}
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie();
    int N;
    cin >> N;
    vector<int> L(N), R(N);
    for(int i = 0; i < N; i++) cin >> L[i] >> R[i], L[i]--, R[i]--;
    vector<vector<int>> byL(N), byR(N);
    for(int i = 0; i < N; i++) byL[L[i]].push_back(i), byR[R[i]].push_back(i);
    vector<int> cl(N), cr(N);
    Seg splSeg(vector<int>(N, inf));
    for(int i = 0; i < N; i++){
        for(int j : byL[i]){
            if(i == 0) cl[j] = 0;
            else cl[j] = splSeg.qry(L[j], R[j]).first + 1;
            splSeg.upd(j, cl[j]);
        }
    }
    splSeg = Seg(vector<int>(N, inf));
    for(int i = N-1; i >= 0; i--){
        for(int j : byR[i]){
            if(i == N-1) cr[j] = 0;
            else cr[j] = splSeg.qry(L[j], R[j]).first + 1;
            splSeg.upd(j, cr[j]);
        }
    }
    vector<int> split(N);
    for(int i = 0; i < N; i++){
        split[i] = cl[i]+cr[i];
    }
    map<int, vector<int>> bySplit;
    for(int i = 0; i < N; i++){
        bySplit[split[i]].push_back(i);
    }


    vector<tuple<int, int, int>> rfi;
    for(int i = 0; i < N; i++){
        rfi.emplace_back(R[i], L[i], i);
    }
    sort(rfi.begin(), rfi.end());
    vector<int> ind(N);
    vector<int> qry_start(N, N);
    vector<int> sinit(N);
    for(int i = 0; i < N; i++){
        auto [r, l, in] = rfi[i];
        ind[in] = i;
        qry_start[r] = min(qry_start[r], i);
        sinit[i] = l;
    }
    for(int i = N-2; i >= 0; i--) qry_start[i] = min(qry_start[i], qry_start[i+1]);
    Seg seg(sinit);
    queue<int> q;
    vector<int> ans(N, -2);
    int cd = 0;
    auto addSplits = [&](){
        for(int i : bySplit[cd]){
            if(ans[i] == -2){
                ans[i] = split[i];
                seg.upd(ind[i], inf);
                q.push(i);
            }
        }
        bySplit[cd].clear();
    };
    while(!q.empty() || cd <= 2*N){
        addSplits();
        if(q.empty()){
            cd++;
            continue;
        }
        int u = q.front();
        // cerr << "# " << u << "\n";
        q.pop();
        if(ans[u] > cd) cd = ans[u];
        addSplits();
        while(true){
            pi p = seg.qry(qry_start[u], N-1);
            if(p.first > u) break;
            int v = get<2>(rfi[p.second]);
            // cerr << v << "\n";
            assert(ans[v] == -2);
            assert(L[v] <= u && u <= R[v]);
            ans[v] = ans[u]+1;
            seg.upd(ind[v], inf);
            q.push(v);
        }
        // for(int v = 0; v < N; v++){
        //     if(ans[v] != -2) continue;
        //     if(L[v] <= u && u <= R[v]){
        //         ans[v] = ans[u]+1;
        //         q.push(v);
        //     }
        // }
    }
    int Q;
    cin >> Q;
    for(int i = 0; i < Q; i++){
        int j;
        cin >> j; j--;
        cout << ans[j]+1 << "\n";
    }
}

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