Submission #1288459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288459		tunademayo	Railway Trip 2 (JOI22_ho_t4)	C++20	0 / 100	347 ms	22672 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define ll long long 
#define ld double

const bool Multitest = 0;

const int N = 1e5 + 10;

vector<int> op[N], cl[N];
int n, k, m, q;

int f[17][N];

struct SegmentTree
{
	int t[4 * N];
	
	void update(int id, int l, int r, int u, int val)
	{
		if(r < u || u < l) return;
		if(l == r)
		{
			t[id] = max(t[id], val);
			return;
		}
		
		int mid = (l + r) >> 1;
		
		update(id * 2, l, mid, u, val);
		update(id * 2 + 1, mid + 1, r, u, val);
		
		t[id] = max(t[id * 2], t[id * 2 + 1]);
	}	
	
	int get(int id, int l, int r, int u, int v)
	{
		if(r < u || v < l) return 0;
		if(u <= l && r <= v) return t[id];
		
		int mid = (l + r) >> 1;
		
		return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
	}
}; SegmentTree st;

void work()
{
	cin >> n >> k >> m;
		
	for(int i = 1 ; i <= m ; i++)
	{
		int l, r;	cin >> l >> r;
		
		if(l < r)
		{
			op[l - 1].push_back(-r);
			cl[min(r - 1, l + k - 1)].push_back(r);
		}
	}
	
	multiset<int> s;
	
	for(int i = n ; i >= 1 ; i--)
	{
		for(auto x : cl[i]) s.insert(x);
		for(auto x : op[i]) s.erase(s.find(-x));
		
		if(!s.empty()) f[0][i] = *s.rbegin();
		else f[0][i] = i;
	}
	
	for(int j = 1 ; j <= 16 ; j++)
	{
		for(int i = 1 ; i <= n ; i++) st.update(1, 1, n, i, f[j - 1][i]);
		
		for(int i = 1 ; i <= n ; i++)
		{
			int nxt = f[j - 1][i];
			
//			cout << i << ' ' << nxt << ' ' << st.get(1, 1, n, i, nxt) << '\n';
			
			f[j][i] = st.get(1, 1, n, i, nxt);
		}
	}
	
//	for(int i = 1 ; i <= n ; i++) cout << f[0][i] << ' '; cout << '\n';
//	
//	cout << f[1][3] << '\n';
	
	int q;	cin >> q;
	while(q--)
	{
		int l, r;	cin >> l >> r;
		
		if(l < r)
		{
			int ans = 0;
			
			for(int i = 16 ; i >= 0 ; i--)
			{
				int nxt = f[i][l];
				
				if(nxt < r) ans |= (1 << i), l = nxt;
			}
			
//			cout << ans << ' ' << l << ' ' << r << '\n';
			
			if(ans == (1 << 17) - 1) cout << -1 << '\n';
			else cout << ans + 1 << '\n';
 		}
	}
}

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

	int q = 1;
	
	if(Multitest)	cin >> q;
	
	while(q--) work();
}

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