Submission #879099

#	Time	Username	Problem	Language	Result	Execution time	Memory
879099		Piokemon	Railway Trip 2 (JOI22_ho_t4)	C++17	25 / 100	1678 ms	44236 KiB

Main

#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,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=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 (stderr)

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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 11
• Subtask 4: 25 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13