oj.uz

Submission #879100

# Submission time Handle Problem Language Result Execution time Memory
879100 2023-11-26T10:54:05 Z Piokemon Railway Trip 2 (JOI22_ho_t4) C++17
25 / 100
 1174 ms 44228 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-1),{1e9,b});
        if (a>b) sed(1,0,1,base,max(a-zas+1,b+1),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 69 ms 43532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 790 ms 43524 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 796 ms 44228 KB Output is correct
2 Correct 963 ms 43604 KB Output is correct
3 Correct 1174 ms 43784 KB Output is correct
4 Correct 711 ms 43528 KB Output is correct
5 Correct 805 ms 43524 KB Output is correct
6 Correct 762 ms 43704 KB Output is correct
7 Correct 1012 ms 43700 KB Output is correct
8 Correct 908 ms 43604 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1133 ms 43528 KB Output is correct
2 Correct 1105 ms 44112 KB Output is correct
3 Correct 1028 ms 43800 KB Output is correct
4 Correct 1037 ms 43780 KB Output is correct
5 Correct 847 ms 43760 KB Output is correct
6 Correct 975 ms 43524 KB Output is correct
7 Correct 921 ms 43532 KB Output is correct
8 Correct 72 ms 43372 KB Output is correct
9 Correct 88 ms 43528 KB Output is correct
10 Correct 882 ms 43524 KB Output is correct
11 Correct 1085 ms 43532 KB Output is correct
12 Correct 1074 ms 43624 KB Output is correct
13 Correct 1121 ms 43588 KB Output is correct
14 Incorrect 78 ms 43608 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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