Submission #877141

#	Time	Username	Problem	Language	Result	Execution time	Memory
877141		Hakiers	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	612 ms	65308 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
constexpr int oo = 1e9;
constexpr int BASE = 1 << 17;
pair<int, int> TREE[BASE << 1][20];
pair<int, int> LAZY[BASE << 1];
pair<int, int> jmp[BASE][20];
int n, z, q, m;

void inittree(){
	for(int k = 0; k < 20; k++)
		for(int i = 0; i < BASE; i++)
			TREE[i+BASE][k] = {i, i};
	
	
	for(int k = 0; k < 20; k++){
		for(int i = BASE-1; i > 0; i--){
			TREE[i][k].fi = min(TREE[i*2][k].fi, TREE[i*2 + 1][k].fi);
			TREE[i][k].se = max(TREE[i*2][k].se, TREE[i*2 + 1][k].se);
		}
	}
	
	for(int i = 0; i < (BASE << 1); i++)
		LAZY[i] = {oo, -oo};
	
}
void push(int v, int l, int r, int k){
	
	TREE[l][k].fi = min(TREE[l][k].fi, LAZY[v].fi);
	TREE[r][k].fi = min(TREE[r][k].fi, LAZY[v].fi);
	TREE[l][k].se = max(TREE[l][k].se, LAZY[v].se);
	TREE[r][k].se = max(TREE[r][k].se, LAZY[v].se);
	
	LAZY[l].fi = min(LAZY[l].fi, LAZY[v].fi);
	LAZY[r].fi = min(LAZY[r].fi, LAZY[v].fi);
	LAZY[l].se = max(LAZY[l].se, LAZY[v].se);
	LAZY[r].se = max(LAZY[r].se, LAZY[v].se);
	
	
	LAZY[v] = {oo, -oo};
}


void update(int v, int l, int r, int a, int b, int val, int k){
	if(r < a || b < l) return;
	else if(a <= l && r <= b){
		TREE[v][k].fi = min(TREE[v][k].fi, val);
		TREE[v][k].se = max(TREE[v][k].se, val);
		LAZY[v].fi = min(LAZY[v].fi, val);
		LAZY[v].se = max(LAZY[v].se, val);
	}
	else{
		int mid = (l+r)/2;
		push(v, 2*v, 2*v + 1, k);
		update(2*v, l, mid, a, b, val, k);
		update(2*v+1, mid+1, r, a, b, val, k);
		
		TREE[v][k].fi = min(TREE[2*v][k].fi, TREE[2*v+1][k].fi);
		TREE[v][k].se = max(TREE[2*v][k].se, TREE[2*v+1][k].se);
	}
}

pair<int, int> query(int v, int l, int r, int a, int b, int k){
	if(r < a || b < l) return {oo, -oo};
	else if(a <= l && r <= b){
		return TREE[v][k];
	}
	else{
		int mid = (l+r)/2;
		push(v, 2*v, 2*v + 1, k);
		pair<int, int> out1 = query(2*v, l, mid, a, b, k);
		pair<int, int> out2 = query(2*v+1, mid+1, r, a, b, k);
		pair<int, int> out3 = {min(out1.fi, out2.fi), max(out1.se, out2.se)};
		
		return out3;
	}
}

pair<int, int> query2(int a, int b, int k){
	a += BASE - 1;
	b += BASE + 1;
	
	pair<int, int> res = {oo, -oo};
	while(a/2 != b/2){
		if(a%2 == 0){
			res.fi = min(res.fi, TREE[a+1][k].fi);
			res.se = max(res.se, TREE[a+1][k].se);
		}
		if(b%2 == 1){
			res.fi = min(res.fi, TREE[b-1][k].fi);
			res.se = max(res.se, TREE[b-1][k].se);
		}
		
		a/=2; b/=2;
	}
	
	return res;
}

void update2(int v, pair<int, int> in, int k){
	v += BASE;
	while(v > 0){
		TREE[v][k].fi = min(TREE[v][k].fi, in.fi);
		TREE[v][k].se = max(TREE[v][k].se, in.se);
		v/= 2;
	}
}

void compute(){

	for(int i = 1; i <= n; i++) jmp[i][0] = query(1, 0, BASE-1, i, i, 0);
	
	for(int k = 1; k <= 19; k++){
		for(int i = 1; i <= n; i++){
			jmp[i][k] = query2(jmp[i][k-1].fi, jmp[i][k-1].se, k-1);
			update2(i, jmp[i][k], k);
		}
	}
}

int query3(int u, int v){
	if(u == v) return 0;
	int res = 0;
	
	pair<int, int> interval = {u, u};
	
	for(int k = 19; k >= 0; k--){
		pair<int, int> ask = query2(interval.fi, interval.se, k);
		if(k == 19 && !(ask.fi <= v && v <= ask.se)) return -1;
		else if(ask.fi <= v && v <= ask.se) continue;
		res += (1 << k);
		interval = ask;
	}
	
	return (res + 1);
}


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	inittree();
	cin >> n >> z;
	cin >> m;
	
	for(int i = 1; i <= m; i++){
		int a, b;
		cin >> a >> b;
		if(a < b) update(1, 0, BASE-1, a, min(a+z-1, b), b, 0);
		else update(1, 0, BASE-1, max(b, a-z+1), a, b, 0);
	}
	compute();
	cin >> q;
	for(int i = 1; i <= q; i++){
		int u, v;
		cin >> u >> v;
		cout << query3(u, v) << "\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