Submission #1055292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055292		Alihan_8	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	1312 ms	196524 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long
 
using i64 = long long;
 
template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}
 
template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}
 
const int inf = 1e9;

const int HT = 18, N = 2e5 * 3;
 
int n;
 
struct SegTree{
	int T[N], p_[N];
 
    SegTree(int random_number){
        for ( int i = 0; i < N; i++ ){
			T[i] = p_[i] = -inf;
		}
    }
    
    void push(int v, int l, int r){
		if ( l != r ){
			chmax(p_[v * 2], p_[v]);
			chmax(p_[v * 2 + 1], p_[v]);
		}
		
		chmax(T[v], p_[v]);
		p_[v] = -inf;
	}
    
    void RngUpd(int v, int l, int r, int tl, int tr, int x){
		push(v, l, r);
		
		if ( l > tr or r < tl ){
			return;
		}
		
		if ( tl <= l && tr >= r ){
			p_[v] = x;
			
			push(v, l, r); 
			
			return;
		}
		
		int m = (l + r) / 2;
		
		RngUpd(v * 2, l, m, tl, tr, x);
		RngUpd(v * 2 + 1, m + 1, r, tl, tr, x);
		
		T[v] = max(T[v * 2], T[v * 2 + 1]);
	}
	
	void RngUpd(int l, int r, int x){
		RngUpd(1, 0, n, l, r, x);
	}
 
    void upd(int v, int l, int r, int p, int x){
		push(v, l, r);
		
        if ( l == r ){
			chmax(T[v], x);
 
            return;
        }
 
        int md = (l + r) >> 1;
 
        if ( p <= md ){
            upd(v * 2, l, md, p, x);
        } else{
            upd(v * 2 + 1, md + 1, r, p, x);
        }
 
        T[v] = max(T[v * 2], T[v * 2 + 1]);
    }
 
    void upd(int p, int x){
        upd(1, 0, n, p, x);
    }
 
    int get(int v, int l, int r, int tl, int tr){
		push(v, l, r);
		
        if ( l > tr or r < tl ){
            return -inf;
        }
 
        if ( tl <= l && tr >= r ){
            return T[v];
        }
 
        int md = (l + r) / 2;
 
        return max(get(v * 2, l, md, tl, tr), get(v * 2 + 1, md + 1, r, tl, tr));
    }
 
    int get(int l, int r){
        return get(1, 0, n, l, r);
    }
};
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int k, m; cin >> n >> k >> m;
 
    vector <int> A(m), B(m);
 
    for ( int i = 0; i < m; i++ ){
        cin >> A[i] >> B[i];
 
        --A[i], --B[i];
    }
 
    vector <SegTree> SegL(HT, SegTree(n * 4 + 5)), SegR(HT, SegTree(n * 4 + 5));
 
    for ( int i = 0; i < m; i++ ){
        if ( A[i] < B[i] ){
            SegR[0].RngUpd(A[i], min(B[i], A[i] + k - 1), B[i]);
        } else{
            SegL[0].RngUpd(max(B[i], A[i] - k + 1), A[i], -B[i]);
        }
    }
 
    vector <vector<int>> upL(n, vector <int> (HT)), upR(n, vector <int> (HT));
	
    for ( int i = 0; i < n; i++ ){
        upL[i][0] = upR[i][0] = i;
        
        chmin(upL[i][0], -SegL[0].get(i, i));
        chmax(upR[i][0], SegR[0].get(i, i));
    }
    
    SegL[0] = SegR[0] = SegTree(n * 4 + 5);
 
	for ( int i = 1; i < HT; i++ ){
		for ( int j = 0; j < n; j++ ){
			SegL[i - 1].upd(j, -upL[j][i - 1]);
			SegR[i - 1].upd(j, upR[j][i - 1]);
		}
		
		for ( int j = 0; j < n; j++ ){
			upL[j][i] = -SegL[i - 1].get(upL[j][i - 1], upR[j][i - 1]);
			upR[j][i] = SegR[i - 1].get(upL[j][i - 1], upR[j][i - 1]);
		}
	}
	
	auto in = [&](int l, int r, int x){
		return l <= x && r >= x;
	};
	
	auto get = [&](int s, int t) -> int{
		if ( !in(upL[s][HT - 1], upR[s][HT - 1], t) ){
			return -1;
		}
		
		int cnt = 0, l = s, r = s;
		
		for ( int i = HT - 2; i >= 0; i-- ){
			int x = -SegL[i].get(l, r), y = SegR[i].get(l, r);
			
			if ( !in(x, y, t) ){
				l = x, r = y;
				
				cnt += 1 << i;
			}
		}
		
		return cnt + !in(l, r, t);
	};
	
	int q; cin >> q;
	
	while ( q-- ){
		int s, t; cin >> s >> t;
		
		--s, --t;
		
		cout << get(s, t) << ln;
	}
 
    cout << '\n';
}

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