oj.uz

Submission #967178

# Submission time Handle Problem Language Result Execution time Memory
967178 2024-04-21T12:19:33 Z SzypkiBill Railway Trip 2 (JOI22_ho_t4) C++17
16 / 100
 2000 ms 116680 KB 
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vb vector<bool>
#define vii vector<pii>
#define siz(x) (int)x.size()
#define pb push_back
#define st first
#define nd second
#define rep(i,a,b) for(int i=a; i<=b; i++)
using namespace std;
const int inf = 1e9, maxn = 1e5+5, mod = 1e9+7;

pii seg[maxn][20];
int base = (1<<17);
int n,k,m;

class segment_tree{
    vi mini;
    vi maxi;
public:
    void init(int p){
        mini.resize(base*2,inf);
        maxi.resize(base*2,-inf);
        rep(i,1,n){
            mini[i+base] = seg[i][p].st;
            maxi[i+base] = seg[i][p].nd;
        }
        for(int i=base-1; i>=1; i--){
            mini[i] = min(mini[i*2],mini[i*2+1]);
            maxi[i] = max(maxi[i*2],maxi[i*2+1]);
        }
    }
    int query_min(int a, int b){
        a+=base-1;b+=base+1;
        int ans = inf;
        while(a/2!=b/2){
            if(!(a&1))ans = min(ans,mini[a+1]);
            if(b&1)ans = min(ans,mini[b-1]);
            a/=2,b/=2;
        }
        return ans;
    }
    int query_max(int a, int b){
        a+=base-1;b+=base+1;
        int ans = -inf;
        while(a/2!=b/2){
            if(!(a&1))ans = max(ans,maxi[a+1]);
            if(b&1)ans = max(ans,maxi[b-1]);
            a/=2,b/=2;
        }
        return ans;
    }
};
class segment_tree_max{
    vi tree;
    public:
    segment_tree_max(){
        tree.resize(2*base);
        rep(i,1,n)tree[i] = i;
    }
    void add(int a, int b, int v){
        rep(i,a,b)tree[i] = max(tree[i],v);
    }
    int query(int a){
        return tree[a];
    }
};
class segment_tree_min{
    vi tree;
    public:
    segment_tree_min(){
        tree.resize(2*base);
        rep(i,1,n)tree[i] = i;
    }
    void add(int a, int b, int v){
        rep(i,a,b)tree[i] = min(tree[i],v);
    }
    int query(int a){
        return tree[a];
    }
};

int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k>>m;
    vii linie;
    rep(i,1,m){
        int a,b;cin>>a>>b;
        linie.pb({a,b});
    }

    segment_tree_max MX;
    for(auto [a,b] : linie){
        if(a<b)
            MX.add(a,min(a+k-1,n),b);
    }
    rep(i,1,n)seg[i][0].nd = MX.query(i);
    segment_tree_min MN;
    for(auto [a,b] : linie){
        if(a>b)
            MN.add(max(1ll,a-k+1),a,b);
    }
    rep(i,1,n)seg[i][0].st = MN.query(i);


    segment_tree tree[20];

    rep(i,1,19){
        tree[i-1].init(i-1);
        rep(j,1,n){
            seg[j][i].st = tree[i-1].query_min(seg[j][i-1].st,seg[j][i-1].nd);
            seg[j][i].nd = tree[i-1].query_max(seg[j][i-1].st,seg[j][i-1].nd);
        }
    }
  /*  rep(i,1,n)cout<<seg[i][2].st<<','<<seg[i][2].nd<<' ';cout<<'\n';
    rep(i,1,n)cout<<seg[i][3].st<<','<<seg[i][3].nd<<' ';cout<<'\n';
    return 0;
*/
    int q;cin>>q;
    rep(i,1,q){
        int a,b;cin>>a>>b;
        int ans = 0;
        pii naj = {a,a};
        for(int j=18; j>=0; j--){
            pii akt;
            akt.st = tree[j].query_min(naj.st,naj.nd);
            akt.nd = tree[j].query_max(naj.st,naj.nd);
            if(b<akt.st || b>akt.nd){
                ans+=(1<<j);
                naj = akt;
            }
        }
        ans++;
        naj.st = tree[0].query_min(naj.st,naj.nd);
        naj.nd = tree[0].query_max(naj.st,naj.nd);
        if(naj.st<=b && naj.nd>=b)cout<<ans<<'\n';
        else cout<<"-1\n";
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 82584 KB Output is correct
2 Correct 35 ms 82600 KB Output is correct
3 Correct 37 ms 82652 KB Output is correct
4 Correct 34 ms 82780 KB Output is correct
5 Correct 35 ms 82740 KB Output is correct
6 Correct 34 ms 82684 KB Output is correct
7 Correct 36 ms 82780 KB Output is correct
8 Correct 39 ms 82768 KB Output is correct
9 Correct 41 ms 82708 KB Output is correct
10 Correct 36 ms 82672 KB Output is correct
11 Correct 44 ms 82748 KB Output is correct
12 Correct 34 ms 82672 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 82584 KB Output is correct
2 Correct 35 ms 82600 KB Output is correct
3 Correct 37 ms 82652 KB Output is correct
4 Correct 34 ms 82780 KB Output is correct
5 Correct 35 ms 82740 KB Output is correct
6 Correct 34 ms 82684 KB Output is correct
7 Correct 36 ms 82780 KB Output is correct
8 Correct 39 ms 82768 KB Output is correct
9 Correct 41 ms 82708 KB Output is correct
10 Correct 36 ms 82672 KB Output is correct
11 Correct 44 ms 82748 KB Output is correct
12 Correct 34 ms 82672 KB Output is correct
13 Correct 39 ms 84820 KB Output is correct
14 Correct 39 ms 84944 KB Output is correct
15 Correct 36 ms 84980 KB Output is correct
16 Correct 40 ms 84828 KB Output is correct
17 Correct 38 ms 84996 KB Output is correct
18 Correct 39 ms 84828 KB Output is correct
19 Correct 41 ms 84940 KB Output is correct
20 Correct 37 ms 84820 KB Output is correct
21 Correct 36 ms 84828 KB Output is correct
22 Correct 48 ms 84912 KB Output is correct
23 Correct 39 ms 84824 KB Output is correct
24 Correct 39 ms 84856 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 115360 KB Output is correct
2 Correct 256 ms 116468 KB Output is correct
3 Correct 293 ms 116680 KB Output is correct
4 Correct 233 ms 115912 KB Output is correct
5 Execution timed out 2057 ms 8772 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2053 ms 3796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2009 ms 5572 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 82584 KB Output is correct
2 Correct 35 ms 82600 KB Output is correct
3 Correct 37 ms 82652 KB Output is correct
4 Correct 34 ms 82780 KB Output is correct
5 Correct 35 ms 82740 KB Output is correct
6 Correct 34 ms 82684 KB Output is correct
7 Correct 36 ms 82780 KB Output is correct
8 Correct 39 ms 82768 KB Output is correct
9 Correct 41 ms 82708 KB Output is correct
10 Correct 36 ms 82672 KB Output is correct
11 Correct 44 ms 82748 KB Output is correct
12 Correct 34 ms 82672 KB Output is correct
13 Correct 39 ms 84820 KB Output is correct
14 Correct 39 ms 84944 KB Output is correct
15 Correct 36 ms 84980 KB Output is correct
16 Correct 40 ms 84828 KB Output is correct
17 Correct 38 ms 84996 KB Output is correct
18 Correct 39 ms 84828 KB Output is correct
19 Correct 41 ms 84940 KB Output is correct
20 Correct 37 ms 84820 KB Output is correct
21 Correct 36 ms 84828 KB Output is correct
22 Correct 48 ms 84912 KB Output is correct
23 Correct 39 ms 84824 KB Output is correct
24 Correct 39 ms 84856 KB Output is correct
25 Correct 252 ms 115360 KB Output is correct
26 Correct 256 ms 116468 KB Output is correct
27 Correct 293 ms 116680 KB Output is correct
28 Correct 233 ms 115912 KB Output is correct
29 Execution timed out 2057 ms 8772 KB Time limit exceeded
30 Halted 0 ms 0 KB -