Submission #1262587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262587		vlomaczk	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	521 ms	39508 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int base = 1<<17;

struct min_left {
	vector<int> t;
	void construct() { t.assign(2*base, INT_MAX); }

	void update(int a, int b, int val) {
		if(a==b) {
			t[a+base] = min(t[a+base], val);
			return;
		}
		a += base-1;
		b += base+1;
		while(a/2 != b/2) {
			if(a%2==0) t[a+1] = min(t[a+1], val);
			if(b%2==1) t[b-1] = min(t[b-1], val);
			a/=2; b/=2;
		}
	}

	int query(int x) {
		int ans = INT_MAX;
		x += base;
		while(x > 0) {
			ans = min(ans, t[x]);
			x/=2;
		}
		return ans;
	}
};

struct max_right {
	vector<int> t;
	void construct() { t.assign(2*base, 0); }

	void update(int a, int b, int val) {
		if(a==b) {
			t[a+base] = max(t[a+base], val);
			return;
		}
		a += base-1;
		b += base+1;
		while(a/2 != b/2) {
			if(a%2==0) t[a+1] = max(t[a+1], val);
			if(b%2==1) t[b-1] = max(t[b-1], val);
			a/=2; b/=2;
		}
	}

	int query(int x) {
		int ans = 0;
		x += base;
		while(x > 0) {
			ans = max(ans, t[x]);
			x/=2;
		}
		return ans;
	}
};

int maxlog = 16;

struct segm_tree_max {
    vector<vector<int>> t;

	void build() {
		t.assign(maxlog+1, vector<int>(2*base, 0));
	}

	void update(int x, int val, int i) {
		x += base;
		t[i][x] = val;
		x/=2;
		while(x>0) {
			t[i][x] = max(t[i][x+x], t[i][x+x+1]);
			x/=2;
		}
	}

	int query(int a, int b, int i) {
		if(a==b) return t[i][a+base];
		a+=base-1;
		b+=base+1;
		int ans = INT_MIN;
		while(a/2!=b/2) {
			if(a%2==0) ans = max(ans, t[i][a+1]);
			if(b%2==1) ans = max(ans, t[i][b-1]);
			a/=2; b/=2;
		}
		return ans;
	}
};

struct segm_tree_min {
	segm_tree_max stm;

	void build() { stm.build(); }
	void update(int x, int val, int i) { stm.update(x, -val, i); }
	int query(int a, int b, int i) { return -stm.query(a, b, i); }
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	ll n, k;
	cin >> n >> k;
	min_left ml; ml.construct();
	max_right mr; mr.construct();
	for(int i=1; i<=n; ++i) {
		mr.update(i, i, i);
		ml.update(i, i, i);
	}
	int m;
	cin >> m;
	for(int i=0; i<m; ++i) {
		ll a, b;
		cin >> a >> b;
		if(a<b) {
			mr.update(a, min(a+k-1, b-1), b);
		} else {
			ml.update(max(a-k+1, b+1), a, b);
		}
	}
	vector<int> vml(n+1), vmr(n+1);
	for(int i=1; i<=n; ++i) {
		vml[i] = ml.query(i);
		vmr[i] = mr.query(i);
	}
	segm_tree_max stmax; stmax.build();
	segm_tree_min stmin; stmin.build();
	for(int i=1; i<=n; ++i) {
		stmax.update(i, vmr[i], 0);
		stmin.update(i, vml[i], 0);
	}
	for(int x=1; x<=maxlog; ++x) {
		for(int i=1; i<=n; ++i) {
			stmax.update(i, stmax.query(stmin.query(i, i, x-1), stmax.query(i, i, x-1), x-1), x);
			stmin.update(i, stmin.query(stmin.query(i, i, x-1), stmax.query(i, i, x-1), x-1), x);
		}
	}
	int q;
	cin >> q;
	while(q--) {
		int a, b;
		cin >> a >> b;
		ll ans = 0;
		pair<int, int> inv = {a, a};
		for(int i=maxlog; i>=0; --i) {
			pair<int, int> new_inv = {stmin.query(inv.first, inv.second, i), stmax.query(inv.first, inv.second, i)};
			if(new_inv.first <= b && b <= new_inv.second) continue;
			inv = new_inv;
			ans += 1LL<<i;
		}
		pair<int, int> new_inv = {stmin.query(inv.first, inv.second, 0), stmax.query(inv.first, inv.second, 0)};
		if(new_inv.first <= b && b <= new_inv.second) cout << ans+1 << "\n";
		else cout << "-1\n";
	}

	return 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