oj.uz

Submission #879097

# Submission time Handle Problem Language Result Execution time Memory
879097 2023-11-26T10:43:14 Z Piokemon Railway Trip 2 (JOI22_ho_t4) C++17
25 / 100
 1597 ms 46836 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); 

    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,k,m,a,b,q;
    cin >> n >> k;
    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+k-1,b-1),{1e9,b});
        if (a>b) sed(1,0,1,base,max(a-k+1,b+1),a,{b,-1e9});
    }
    for (int x=0;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;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:87:27: warning: variable 'xd' set but not used [-Wunused-but-set-variable]
   87 |             pair<int,int> xd = query(1,k,1,base,x,x);
      |                           ^~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1191 ms 44476 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 1238 ms 45196 KB Output is correct
2 Correct 1403 ms 46340 KB Output is correct
3 Correct 1597 ms 45440 KB Output is correct
4 Correct 1122 ms 46120 KB Output is correct
5 Correct 1188 ms 46408 KB Output is correct
6 Correct 1142 ms 46332 KB Output is correct
7 Correct 1422 ms 46836 KB Output is correct
8 Correct 1308 ms 46656 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1590 ms 46604 KB Output is correct
2 Correct 1533 ms 45664 KB Output is correct
3 Correct 1436 ms 44920 KB Output is correct
4 Correct 1456 ms 44464 KB Output is correct
5 Correct 1270 ms 44276 KB Output is correct
6 Correct 1427 ms 44112 KB Output is correct
7 Correct 1389 ms 45176 KB Output is correct
8 Correct 71 ms 43536 KB Output is correct
9 Correct 93 ms 43564 KB Output is correct
10 Correct 1304 ms 45828 KB Output is correct
11 Correct 1463 ms 46332 KB Output is correct
12 Correct 1497 ms 46416 KB Output is correct
13 Correct 1497 ms 46584 KB Output is correct
14 Incorrect 67 ms 43352 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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