oj.uz

Submission #879127

# Submission time Handle Problem Language Result Execution time Memory
879127 2023-11-26T12:04:16 Z Piokemon Railway Trip 2 (JOI22_ho_t4) C++17
25 / 100
 1156 ms 43872 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

constexpr int M = 2e5;
constexpr int K = 20;
constexpr int base = (1<<17);
pair<int,int> tree[2*base+9][K];
pair<int,int> lazy[2*base+9];

void daj(int x, int k){
    tree[2*x][k].first = min(tree[2*x][k].first,lazy[x].first); 
    tree[2*x][k].second = max(tree[2*x][k].second,lazy[x].second); 
    lazy[2*x].first = min(lazy[2*x].first,lazy[x].first); 
    lazy[2*x].second = max(lazy[2*x].second,lazy[x].second);

    tree[2*x+1][k].first = min(tree[2*x+1][k].first,lazy[x].first); 
    tree[2*x+1][k].second = max(tree[2*x+1][k].second,lazy[x].second); 
    lazy[2*x+1].first = min(lazy[2*x+1].first,lazy[x].first); 
    lazy[2*x+1].second = max(lazy[2*x+1].second,lazy[x].second); 

    tree[x][k].first = min(tree[2*x][k].first,tree[2*x+1][k].first);
    tree[x][k].second = max(tree[2*x][k].second,tree[2*x+1][k].second);

    lazy[x] = {1e9,-1e9};
}

void sed(int x, int l, int a, int b, int p, int k, pair<int,int> val){
    if (p<=a && b<=k){
        tree[x][l].first = min(tree[x][l].first,val.first);
        tree[x][l].second = max(tree[x][l].second,val.second);
        lazy[x].first = min(lazy[x].first,val.first);
        lazy[x].second = max(lazy[x].second,val.second);
        return;
    }
    if (b<p || a>k) return;
    daj(x,l);
    int mid=(a+b)/2;
    sed(2*x,l,a,mid,p,k,val);
    sed(2*x+1,l,mid+1,b,p,k,val);
    tree[x][l].first = min(tree[2*x][l].first,tree[2*x+1][l].first);
    tree[x][l].second = max(tree[2*x][l].second,tree[2*x+1][l].second);
}

pair<int,int> query(int x, int l, int a, int b, int p, int k){
    if (p<=a && b<=k) return tree[x][l];
    if (b<p || a>k) return {1e9,-1e9};
    int mid=(a+b)/2;
    if (l==0) daj(x,l);
    pair<int,int> j = query(2*x,l,a,mid,p,k);
    pair<int,int> d = query(2*x+1,l,mid+1,b,p,k);
    tree[x][l].first = min(tree[2*x][l].first,tree[2*x+1][l].first);
    tree[x][l].second = max(tree[2*x][l].second,tree[2*x+1][l].second);
    return {min(j.first,d.first),max(j.second,d.second)};
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,zas,m,a,b,q;
    cin >> n >> zas;
    cin >> m;
    for (int k=0;k<K;k++){
        for (int x=0;x<=2*base;x++) tree[x][k] = {1e9,-1e9};
    }
    for (int x=0;x<=2*base;x++) lazy[x] = {1e9,-1e9};
    for (int x=1;x<=n;x++) tree[x+base-1][0] = {x,x};
    for (int x=base-1;x>=1;x--){
            tree[x][0].first = min(tree[2*x][0].first,tree[2*x+1][0].second);
            tree[x][0].second = max(tree[2*x][0].first,tree[2*x+1][0].second);
        }
    for (int x=0;x<m;x++){
        cin >> a >> b;
        if (a<b) sed(1,0,1,base,a,min(a+zas-1,b),{1e9,b});
        if (a>b) sed(1,0,1,base,max(a-zas+1,b),a,{b,-1e9});
    }
    for (int x=1;x<base;x++) daj(x,0);
    for (int k=1;k<K;k++){
        for (int x=1;x<=n;x++){
            tree[x+base-1][k] = query(1,k-1,1,base,tree[x+base-1][k-1].first,tree[x+base-1][k-1].second);
        }
        for (int x=base-1;x>=1;x--){
            tree[x][k].first = min(tree[2*x][k].first,tree[2*x+1][k].second);
            tree[x][k].second = max(tree[2*x][k].first,tree[2*x+1][k].second);
        }
    }
    /*for (int k=0;k<K;k++){
        for (int x=1;x<=n;x++){
            pair<int,int> xd = query(1,k,1,base,x,x);
            cout << x << ' ' << (1<<k) << ' ' << xd.first << ' ' << xd.second << '\n';
        }
    }*/
    cin >> q;
    while(q--){
        cin >> a >> b;
        int odp=0;
        pair<int,int> range = {a,a};
        for (int k=K-1;k>=0;k--){
            pair<int,int> temp = query(1,k,1,base,range.first,range.second);
            if (!(temp.first <= b && b <= temp.second)){
                odp += (1<<k);
                range =temp;
            }
        }
        if (odp+1 == (1<<K)) cout << "-1\n";
        else cout << odp+1 << '\n';
    }
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 43352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 43352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 781 ms 43528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 849 ms 43668 KB Output is correct
2 Correct 948 ms 43620 KB Output is correct
3 Correct 1156 ms 43784 KB Output is correct
4 Correct 642 ms 43536 KB Output is correct
5 Correct 728 ms 43672 KB Output is correct
6 Correct 736 ms 43604 KB Output is correct
7 Correct 990 ms 43604 KB Output is correct
8 Correct 858 ms 43600 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1122 ms 43528 KB Output is correct
2 Correct 1094 ms 43784 KB Output is correct
3 Correct 992 ms 43788 KB Output is correct
4 Correct 1014 ms 43704 KB Output is correct
5 Correct 818 ms 43604 KB Output is correct
6 Correct 952 ms 43528 KB Output is correct
7 Correct 920 ms 43600 KB Output is correct
8 Correct 67 ms 43352 KB Output is correct
9 Correct 84 ms 43528 KB Output is correct
10 Correct 813 ms 43524 KB Output is correct
11 Correct 1020 ms 43604 KB Output is correct
12 Correct 1075 ms 43528 KB Output is correct
13 Correct 1018 ms 43872 KB Output is correct
14 Incorrect 68 ms 43528 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 43352 KB Output isn't correct
2 Halted 0 ms 0 KB -