Submission #884478

#	Time	Username	Problem	Language	Result	Execution time	Memory
884478		efedmrlr	Passport (JOI23_passport)	C++17	100 / 100	767 ms	130204 KiB

passport

#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 2e5+5;
const int ALPH = 26;
const int LGN = 25;
const int MOD = 1e9+7;
int n,m,q;

vector<int> que;
vector<int> dp;
vector<int> dpL, dpR;

void dbg(vector<int> x) {
    for(auto c : x) {
        cout<<c<<" ";
    }
    cout<<"\n";
} 

struct NodeTree {
    vector<vector<int> > data;
    vector<int> vis;
    int sz;
    NodeTree(int sz) {
        data.assign(4*(sz + 3), vector<int>());
        this->sz = sz;
        vis.assign(sz + 3, 0);
    }
    void update(int tl, int tr, int v, int l, int r, int node) {
        if(tl >= l && tr <= r) {
            data[v].pb(node);
            return;
        }
        if(tl > r || tr < l) {
            return;
        }
        int tm = (tl + tr) >> 1;
        update(tl, tm, v*2, l, r, node);
        update(tm + 1, tr, v*2+1, l, r, node);
    }
    void update(int l, int r, int node) {
        update(0, sz, 1, l, r, node);
    }

    void query(int tl, int tr, int v, int ind, vector<int> &vec) {
        while(data[v].size()) {
            if(!vis[data[v].back()]) {
                vis[data[v].back()] = 1;
                vec.pb(data[v].back());
            }
            data[v].pop_back();
        }
        if(tl == tr) {   
            return;
        }
        int tm = (tl + tr) >> 1;
        if(ind <= tm) {
            query(tl, tm, v*2, ind, vec);
        }
        else {
            query(tm + 1, tr, v*2+1, ind, vec);
        }  
        
    }
    void query(int ind, vector<int> &vec) {
        query(0, sz, 1, ind, vec);
    }
};


struct Inter {
    int l, r, ind;
    Inter(int l, int r, int i) {
        this->l = l;
        this->r = r;
        this->ind = i;
    }
    Inter() {
        l = 0; r = 0; ind = 0;
    }
    void input(int i) {
        cin>>l>>r;
        ind = i;
    }
    void print() {
        cout<<"INTERVAL\n";
        cout<<"l:"<<l<<" r:"<<r<<" ind:"<<ind<<"\n";
    }
};

vector<Inter> inter;

void find_sp(vector<int> &src, vector<int> &sp, NodeTree &st) {
    queue<int> ord;
    sp.assign(n + 3, INF);
    // cout<<"src:\n";
    // dbg(src);
    for(auto c : src) {
        ord.push(c);
        sp[c] = 0;
    }
    while(ord.size()) {
        auto cur = ord.front();
        ord.pop();
        vector<int> ch;
        
        st.query(cur , ch);
        // cout<<"cur:"<<cur<<" ch:\n";
        // dbg(ch);
        for(auto c : ch) {
            sp[c] = sp[cur] + 1;
            ord.push(c);
        }
    }
}


void bfs(vector<array<int,2> > &entr, vector<int> &sp, NodeTree &st) { // find sp with entry times
    queue<int> ord;
    sort(entr.rbegin(), entr.rend());
    // cout<<"ENTR:\n";
    // for(auto c : entr) {
    //     cout<<c[0]<<" "<<c[1]<<"\n";
    // }

    sp.assign(n+3, INF);

    ord.push(entr.back()[1]);
    sp[entr.back()[1]] = entr.back()[0];
    st.vis[entr.back()[1]] = 1;
    entr.pop_back();

    
    while(ord.size()) {
        auto cur = ord.front();
        ord.pop();
        while(entr.size() && entr.back()[0] <= sp[cur]) {
            if(st.vis[entr.back()[1]]) {
                entr.pop_back();
                continue;
            }
            ord.push(entr.back()[1]);
            sp[entr.back()[1]] = entr.back()[0];
            st.vis[entr.back()[1]] = 1;
            entr.pop_back(); 
        }
        vector<int> ch;
        st.query(cur, ch);
        for(auto c : ch) {
            ord.push(c);
            sp[c] = sp[cur] + 1;

        }

    }
}
void prec() {
    NodeTree Ltree(n), Rtree(n);
    vector<int> src;
    for(int i = 1; i<=n; i++) {
        if(inter[i].l == 1) {
            src.pb(i);
        }
        else {
            Ltree.update(inter[i].l, inter[i].r, i);
        }
    }
    find_sp(src, dpL, Ltree);
    src.clear();
    for(int i = 1; i<=n; i++) {
        if(inter[i].r == n) {
            src.pb(i);
        } 
        else {
            Rtree.update(inter[i].l, inter[i].r, i);
        }
    }
    find_sp(src, dpR, Rtree);
    vector<array<int,2> > entr(n);
    NodeTree nt(n);
    
    for(int i = 1; i<=n; i++) {
        entr[i - 1] = {dpL[i] + dpR[i], i};
        nt.update(inter[i].l, inter[i].r, i);
    }
    bfs(entr, dp, nt);


}

inline void solve() {
    cin>>n;
    inter.assign(n + 1, Inter());
    REP(i,n) {
        inter[i + 1].input(i + 1);
    }
    cin>>q;
    que.assign(q+3, 0);
    REP(i,q) {
        cin>>que[i + 1];
    }
    prec();
    // cout<<"dpL:\n";
    // dbg(dpL);
    // cout<<"dpR:\n";
    // dbg(dpR);
    // cout<<"dp:\n";
    // dbg(dp);
    for(int i = 1; i<=q; i++) {
        if(dp[que[i]] == INF) dp[que[i]] = -2;
        cout<<dp[que[i]] + 1<<"\n"; 
    }
    
}
 
signed main() {

    fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

Compilation message (stderr)

passport.cpp: In function 'void solve()':
passport.cpp:9:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)
      |                          ^
passport.cpp:210:5: note: in expansion of macro 'REP'
  210 |     REP(i,n) {
      |     ^~~
passport.cpp:9:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define REP(i,n) for(int (i) = 0; (i) < (n); (i)++)
      |                          ^
passport.cpp:215:5: note: in expansion of macro 'REP'
  215 |     REP(i,q) {
      |     ^~~

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