제출 #1288493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288493		tunademayo	Railway Trip 2 (JOI22_ho_t4)	C++20	0 / 100	1037 ms	50036 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, POS[N];

int f[18][N], ans[N];

struct SegmentTree
{
	int t[4 * N];
	
	void init()
	{
		for(int i = 1 ; i < 4 * N ; i++) t[i] = 0;
	}
	
	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;
}

struct Line
{
	int l, r;
}; Line a[N];

struct Queries
{
	int l, r;
}; Queries t[N];

void pre()
{
	for(int i = 1 ; i <= n ; i++)
	{
		op[i].clear();
		cl[i].clear();
	}
	
	for(int i = 0 ; i <= 17 ; i++)
	{
		for(int j = 1 ; j <= n ; j++)
		{
			f[i][j] = 0;	
		}
		st[i].init();
	}
}

void process()
{
	for(int i = 1 ; i <= m ; i++)
	{
		int l = a[i].l, r = a[i].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];
			
			f[j][i] = st[j - 1].get(1, 1, n, i, nxt);
		}
	}
	
	for(int i = 1 ; i <= q ;  i++)
	{
		int l = t[i].l, r = t[i].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;
			}
			
			ans[i] = pos;
 		}
	}
}

void work()
{
	cin >> n >> k >> m;
//	cerr << "done" << '\n';	
	pre();
		
	for(int i = 1 ; i <= m ; i++)
	{
		cin >> a[i].l >> a[i].r;
	} 
	
	for(int i = 1, j = n ; i <= n ; i++, j--)
	{
		POS[j] = i;
	}
//	cerr << "done" << '\n';
	cin >> q;
	for(int i = 1 ; i <= q ; i++) cin >> t[i].l >> t[i].r;
	
	process();
	for(int i = 1 ; i <= m ; i++)
	{
		a[i].l = POS[a[i].l];
		a[i].r = POS[a[i].r];
	}
	
	for(int i = 1 ; i <= q ; i++)
	{
		t[i].l = POS[t[i].l];
		t[i].r = POS[t[i].r];
	}
	process();
	
	for(int i = 1 ; i <= q ; i++) cout << ans[i] << '\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