제출 #1288492

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288492		tunademayo	Railway Trip 2 (JOI22_ho_t4)	C++20	35 / 100	1033 ms	40612 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[18][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[18];

int lift(int u, int cnt)
{
	if(cnt == 0) return u;
	
	int v = __builtin_ctz(cnt & (-cnt)), r = f[v][u];
	
	for(int i = v + 1 ; i <= 17 ; i++)
	{
		if((cnt >> i) & 1)
		{
			r = st[i].get(1, 1, n, u, r);
		}
	}
	
	return r;
}

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 <= 18 ; j++)
	{
		for(int i = 1 ; i <= n ; i++) st[j - 1].update(1, 1, n, i, f[j - 1][i]);
		
		if(j > 17) break;
		
		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[j - 1].get(1, 1, n, i, nxt);
		}
	}
	
//	for(int i = 1 ; i <= n ; i++) cout << f[0][i] << ' '; cout << '\n';
//	
//	cout << f[1][3] << '\n';
	
//	cout << lift(3, 2) << '\n';
//	
//	return;
	
	int q;	cin >> q;
	while(q--)
	{
		int l, r;	cin >> l >> r;
		
		if(l < r)
		{
			int ans = 0;
			
			int li = 0, ri = n, pos = -1;
			
			while(li <= ri)
			{
				int mid = (li + ri) >> 1;
				
				if(lift(l, mid) >= r) ri = mid - 1, pos = mid;
				else li = mid + 1;
			}
			
			cout << pos << '\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: 35 / 35
• Subtask 6: 0 / 13