Submission #974200

#	Time	Username	Problem	Language	Result	Execution time	Memory
974200		berr	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	601 ms	64568 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 505;

struct segtree{
    int n, tl, tr, type;
    vector<int> st, a;

    int merge(int x, int y){
        if(type==0) return min(x, y);
        return max(x, y);
    }

    segtree(vector<int> x, int t){
        n=x.size(); type = t;
        a=x; st.resize(2*n);

        for(int i=0; i<n; i++) st[i+n]=x[i];

        for(int i=n-1; i>=0; i--) st[i]=merge(st[i*2], st[i*2+1]);
    }
    int operator()(int l, int r){
        int base=a[l];

        for(l+=n, r+=n+1; l!=r; l/=2, r/=2){
            if(l&1) base=merge(base, st[l++]);
            if(r&1) base=merge(base, st[--r]);
        }

        return base;
    }
};
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k, m; cin >> n >> k >> m;

    vector<int> l(n), r(n);

    priority_queue<array<int, 2>> q;

    iota(l.begin(), l.end(), 0);
    iota(r.begin(), r.end(), 0);

    vector<array<int, 2>> e(m);

    for(auto &[i, l]: e) cin >> i >> l, i--, l--;

    sort(e.begin(), e.end());

    int pos=0;

    for(int i=0; i<n; i++){
        while(pos<m && e[pos][0]==i)
            q.push({e[pos][1], e[pos][0]}), pos++;
        
        while(q.size()&&q.top()[1] < i-k+1)
            q.pop();
        if(q.size())
        if(q.size()) r[i]=max(r[i], q.top()[0]);
    }

    while(q.size()) q.pop();
    
    reverse(e.begin(), e.end());

    pos = 0;

    for(int i=n-1; i>=0; i--){
        while(pos<m && e[pos][0]==i)
            q.push({-e[pos][1], e[pos][0]}), pos++;
        
        while(q.size()&&q.top()[1] > i+k-1)
            q.pop();
        
        if(q.size()) l[i]=min(l[i], -q.top()[0]);
    }

    vector<vector<int>> left, right;
    left.push_back(l);
    right.push_back(r);
    vector<segtree> left_st, right_st;

    for(int i=1; i<=n; i*=2){
       segtree l(left.back(), 0), r(right.back(), 1);
       vector<int> l_new(n), r_new(n);
       for(int i=0; i<n; i++){
            l_new[i]=l(left.back()[i], right.back()[i]);
            r_new[i]=r(left.back()[i], right.back()[i]);
       }    
       left_st.push_back(l); right_st.push_back(r);
       left.push_back(l_new);
       right.push_back(r_new);
    }

    int qe; cin >> qe;

    while(qe--){
        int x, y; cin >> x >> y;
        x--; y--;

        int s=0;    
        int le=-1, re=-1, pos=-1, ans=0;
        for(int i=left.size()-1; i>=0; i--){
            int tl=left[i][x],  tr=right[i][x];

            if(tl<= y&&y<=tr)
                continue;
            else{
                le=tl; re=tr;
                pos=i; ans+=(1<<i);
                break;
            }
        }
        
        if(le==-1 && re==-1) cout<<1<<"\n";
        else{
            
            for(int i=pos-1; i>=0; i--){
                int vl=left_st[i](le, re), vr=right_st[i](le, re);

                if(vl <= y && y<=vr){
                    continue;
                }
                else{
                    le=min(vl, le); re=max(re, vr);
                    ans+=(1<<i);
                }
            }

            ans++;
            int tl=(left_st[0](le, re));
            int tr=right_st[0](le, re);

            if(tl<=y&&y<=tr) cout<<ans<<"\n";
            else cout<<-1<<"\n";
        }


    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:103:13: warning: unused variable 's' [-Wunused-variable]
  103 |         int s=0;
      |             ^

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13