oj.uz

Submission #884478

# Submission time Handle Problem Language Result Execution time Memory
884478 2023-12-07T13:12:44 Z efedmrlr Passport (JOI23_passport) C++17
100 / 100
 767 ms 130204 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 721 ms 127476 KB Output is correct
5 Correct 307 ms 98448 KB Output is correct
6 Correct 241 ms 99668 KB Output is correct
7 Correct 118 ms 82840 KB Output is correct
8 Correct 86 ms 68504 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 708 KB Output is correct
9 Correct 0 ms 500 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 708 KB Output is correct
9 Correct 0 ms 500 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 4 ms 1628 KB Output is correct
17 Correct 4 ms 1628 KB Output is correct
18 Correct 4 ms 2136 KB Output is correct
19 Correct 4 ms 1884 KB Output is correct
20 Correct 3 ms 1880 KB Output is correct
21 Correct 3 ms 1628 KB Output is correct
22 Correct 2 ms 1372 KB Output is correct
23 Correct 3 ms 1796 KB Output is correct
24 Correct 3 ms 1624 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 708 KB Output is correct
9 Correct 0 ms 500 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 4 ms 1628 KB Output is correct
17 Correct 4 ms 1628 KB Output is correct
18 Correct 4 ms 2136 KB Output is correct
19 Correct 4 ms 1884 KB Output is correct
20 Correct 3 ms 1880 KB Output is correct
21 Correct 3 ms 1628 KB Output is correct
22 Correct 2 ms 1372 KB Output is correct
23 Correct 3 ms 1796 KB Output is correct
24 Correct 3 ms 1624 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 5 ms 1628 KB Output is correct
28 Correct 4 ms 1496 KB Output is correct
29 Correct 3 ms 1628 KB Output is correct
30 Correct 3 ms 1628 KB Output is correct
31 Correct 5 ms 1628 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 721 ms 127476 KB Output is correct
5 Correct 307 ms 98448 KB Output is correct
6 Correct 241 ms 99668 KB Output is correct
7 Correct 118 ms 82840 KB Output is correct
8 Correct 86 ms 68504 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 708 KB Output is correct
17 Correct 0 ms 500 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 4 ms 1628 KB Output is correct
25 Correct 4 ms 1628 KB Output is correct
26 Correct 4 ms 2136 KB Output is correct
27 Correct 4 ms 1884 KB Output is correct
28 Correct 3 ms 1880 KB Output is correct
29 Correct 3 ms 1628 KB Output is correct
30 Correct 2 ms 1372 KB Output is correct
31 Correct 3 ms 1796 KB Output is correct
32 Correct 3 ms 1624 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 5 ms 1628 KB Output is correct
36 Correct 4 ms 1496 KB Output is correct
37 Correct 3 ms 1628 KB Output is correct
38 Correct 3 ms 1628 KB Output is correct
39 Correct 5 ms 1628 KB Output is correct
40 Correct 767 ms 130204 KB Output is correct
41 Correct 352 ms 101468 KB Output is correct
42 Correct 435 ms 129724 KB Output is correct
43 Correct 466 ms 130076 KB Output is correct
44 Correct 272 ms 101740 KB Output is correct
45 Correct 290 ms 104380 KB Output is correct
46 Correct 100 ms 37732 KB Output is correct
47 Correct 308 ms 108968 KB Output is correct
48 Correct 345 ms 107312 KB Output is correct