Submission #883876

#	Time	Username	Problem	Language	Result	Execution time	Memory
883876		vjudge1	Passport (JOI23_passport)	C++17	0 / 100	2104 ms	167128 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, int bd) {
    for(int i = 0; i<min((int)x.size(), bd); i++) {
        cout << x[i]<<" ";
    }
    cout<<"\n";
} 
void dbg(vector<int> x) {
    for(int i = 0; i<x.size(); i++) {
        cout << x[i]<<" ";
    }
    cout<<"end\n";
} 
struct SegTree {
    vector<int> data;
    int sz;
    SegTree(int sz) {
        this->sz = sz;
        data.assign(4*(sz + 5), INF);
    }
    void reset() {
        data.assign(4*(sz + 5), INF);
    }
    void update(int tl, int tr, int v, int ind, int val) {
        if(tl == tr) {
            data[v] = val;
            return;
        }
        int tm = (tl + tr) >> 1;
        if(ind <= tm) {
            update(tl, tm, v*2, ind, val);
        }
        else {
            update(tm + 1, tr, v*2+1, ind, val);
        }
        data[v] = min(data[v*2], data[v*2+1]);
    }
    void update(int ind, int val) {
        update(0, sz, 1, ind, val);
    }

    int query(int tl, int tr, int v, int l, int r) {
        if(tl >= l && tr <= r) {
            return data[v];
        }
        if(tl > r || tr < l) {
            return INF;
        }
        int tm = (tl + tr) >> 1;
        return min(query(tl, tm, v*2, l, r), query(tm + 1, tr, v*2+1, l, r));
    }
    int query(int l, int r) {
        return query(0, sz, 1, l, r);
    }
}; 

struct SegTreeArr {
    vector<array<int,3> > data;
    int sz;
    SegTreeArr(int sz) {
        this->sz = sz;
        data.assign(4*(sz + 5), {INF,INF,INF});
    }
    void reset() {
        data.assign(4*(sz + 5), {INF,INF,INF});
    }
    void update(int tl, int tr, int v, int ind, array<int,3> val) {
        if(tl == tr) {
            data[v] = val;
            return;
        }
        int tm = (tl + tr) >> 1;
        if(ind <= tm) {
            update(tl, tm, v*2, ind, val);
        }
        else {
            update(tm + 1, tr, v*2+1, ind, val);
        }
        data[v] = min(data[v*2], data[v*2+1]);
    }
    void update(int ind, array<int,3> val) {
        update(0, sz, 1, ind, val);
    }

    array<int,3> query(int tl, int tr, int v, int l, int r) {
        if(tl >= l && tr <= r) {
            return data[v];
        }
        if(tl > r || tr < l) {
            return {INF,INF,INF};
        }
        int tm = (tl + tr) >> 1;
        return min(query(tl, tm, v*2, l, r), query(tm + 1, tr, v*2+1, l, r));
    }
    int query(int l, int r) {
        return query(0, sz, 1, l, r)[2];
    }
}; 

struct NodeTree {
    vector<set<int> > data;
    int sz;
    NodeTree(int sz) {
        data.assign(4*(sz + 3), set<int>());
        this->sz = sz;
    }
    void update(int tl, int tr, int v, int l, int r, int node) {
        if(tl >= l && tr <= r) {
            data[v].insert(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 erase(int tl, int tr, int v, int l, int r, int node) {
        if(tl >= l && tr <= r) {
            assert(data[v].count(node));
            data[v].erase(node);
            return;
        }
        if(tl > r || tr < l) {
            return;
        }
        int tm = (tl + tr) >> 1;
        erase(tl, tm, v*2, l, r, node);
        erase(tm + 1, tr, v*2+1, l, r, node);    
    } 
    void erase(int l, int r, int node) {
        erase(0, sz, 1, l, r, node);
    }
    void query(int tl, int tr, int v, int ind, vector<int> &vec) {
        if(tl == tr) {
            for(auto c : data[v]) {
                vec.pb(c);
            }
            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);
        }  
        for(auto c : data[v]) {
            vec.pb(c);
        }
    }
    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;
    }
    const bool operator<(const Inter &oth) {
        return r - l < oth.r - oth.l;
    }
    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;
vector<Inter> ints;
SegTree *segdp;
SegTreeArr *segl, *segr;
void f(Inter cur) {
    if(cur.l == 1 && cur.r == n) {
        dp[cur.ind] = 0;
        return;
    }
    dp[cur.ind] = INF;
    dp[cur.ind] = min(dp[cur.ind], segdp->query(cur.l,cur.r) + 1);
    // cur.print();
    int mxl = segl->query(cur.l,cur.r);
    int mxr = segr->query(cur.l,cur.r);
    // cout<<"segdp:"<<dp[cur.ind]<<"\n";
    // cout<<"mxl ind:"<<mxl<<"\n";
    // ints[mxl].print();
    // cout<<"mxr ind:"<<mxr<<"\n";
    // ints[mxr].print();

    dp[cur.ind] = min(dp[cur.ind] , (cur.l == 1 ? 0 : (min(dpL[mxl] , dpL[mxr]) + 1)) + (cur.r == n ? 0 : (min(dpR[mxl] , dpR[mxr]) + 1)) );
    dp[cur.ind] = min(dp[cur.ind] , (cur.l == 1 ? 0 : dpL[mxl]) + (cur.r == n ? 0 : dpR[mxl]) + 1);
    dp[cur.ind] = min(dp[cur.ind] , (cur.l == 1 ? 0 : dpL[mxr]) + (cur.r == n ? 0 : dpR[mxr]) + 1);
    
    // cout<<"dp:"<<dp[cur.ind]<<"\n";
}

void calcL() {
    queue<int> bfs;
    dpL.assign(n+3, INF);
    NodeTree nt(n);    
    for(int i = 1; i<=n; i++) {
        if(inter[i].l == 1) {
            dpL[i] = 0;
            bfs.push(i);
        }
        else {
            nt.update(inter[i].l, inter[i].r, i);
        }
    }
    while(bfs.size()) {
        auto cur = bfs.front();
        bfs.pop();
        vector<int> ch;
        nt.query(cur, ch);
        for(auto c : ch) {
            dpL[c] = dpL[cur] + 1;
            bfs.push(c);
            nt.erase(inter[c].l, inter[c].r, c);
        }
    }
}
void calcR() {
    queue<int> bfs;
    dpR.assign(n+3, INF);
    NodeTree nt(n);    
    for(int i = 1; i<=n; i++) {
        if(inter[i].r == n) {
            dpR[i] = 0;
            bfs.push(i);
        }
        else {
            nt.update(inter[i].l, inter[i].r, i);
        }
    }
    while(bfs.size()) {
        auto cur = bfs.front();
        bfs.pop();
        vector<int> ch;
        nt.query(cur, ch);
        for(auto c : ch) {
            dpR[c] = dpR[cur] + 1;
            bfs.push(c);
            nt.erase(inter[c].l, inter[c].r, c);
        }
    }
}
void prec() {
    calcL();
    calcR();
    // dbg(dpL);
    // dbg(dpR);
    ints = inter;
    inter.erase(inter.begin());
    segdp = new SegTree(n); //min
    segl = new SegTreeArr(n); //min
    segr = new SegTreeArr(n); //max
    dp.assign(n+3, 0);
    sort(inter.rbegin(), inter.rend());

    for(auto c : inter) {
        segl->update(c.ind, {c.l, -c.r, c.ind});
        segr->update(c.ind, {-c.r, c.l, c.ind});
    }
    
    for(auto c : inter) {
        //c.print();

        f(c);
        segdp->update(c.ind, dp[c.ind]);

    }
}


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();
    for(int i = 1; i<=q; i++) {
        auto cur = que[i];
        dp[cur]++;
        if(dp[cur] >= INF) dp[cur] = -1;
        cout<<dp[cur]<<"\n";
    }
}
 
signed main() {

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

Compilation message (stderr)

passport.cpp: In function 'void dbg(std::vector<int>)':
passport.cpp:36:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i = 0; i<x.size(); i++) {
      |                    ~^~~~~~~~~
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:320:5: note: in expansion of macro 'REP'
  320 |     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:325:5: note: in expansion of macro 'REP'
  325 |     REP(i,q) {
      |     ^~~

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