Submission #1288527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288527		tunademayo	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	1027 ms	152156 KiB

Main

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

#define ll long long 
#define ld double

const bool Multitest = 0;

const int N = 2e5 + 10;

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

int f[20][N], g[20][N], ans[N];

struct SegmentTree
{
	int t[4 * N]; bool Type;
	
	int merge(int a, int b)
	{
		if(Type == 1) return max(a, b);
		return min(a, b);	
	}
	
	void init(bool _Type)
	{
		Type = _Type;
		for(int i = 1 ; i < 4 * N ; i++)
		{
			if(Type == 1) t[i] = 0;
			else t[i] = 1e9;  
		}
	}
	
	void update(int id, int l, int r, int u, int val)
	{
		if(r < u || u < l) return;
		if(l == r)
		{
			t[id] = merge(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] = merge(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 Type == 1 ? 0 : 1e9;
		if(u <= l && r <= v) return t[id];
		
		int mid = (l + r) >> 1;
		
		return merge(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
	}
}; SegmentTree st[18], st1[18];

int lift(int u, int cnt)
{
	if(cnt == 0) return u;
	
	int v = __builtin_ctz(cnt & (-cnt)), r = f[v][u], l = g[v][u];
	
	for(int i = v + 1 ; i <= 17 ; i++)
	{
		if((cnt >> i) & 1)
		{
			int L = l, R = r;
			r = st[i].get(1, 1, n, L, R);
			l = st1[i].get(1, 1, n, L, 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();
		op1[i].clear();
		cl1[i].clear();
	}
	
	for(int i = 0 ; i <= 17 ; i++)
	{
		for(int j = 1 ; j <= n ; j++)
		{
			f[i][j] = 0;	
			g[i][j] = 0;
		}
		st[i].init(1);
		st1[i].init(0);
	}
}

void process()
{
	pre();
//	cerr << "okay" << "\n";
	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);
		}
		else 
		{
			swap(l, r);
			
			op1[r + 1].push_back(-l);
			cl1[max(l + 1, r - k + 1)].push_back(l);
			
			swap(l, r);
		}
	}
//	cerr << "okay" << '\n';
	
	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;
	}
	
	s.clear();
	
	for(int i = 1 ; i <= n ; i++)
	{
		for(auto x : cl1[i]) s.insert(x);
		for(auto x : op1[i]) s.erase(s.find(-x));
		
//		cerr << i << '\n';
		
		if(!s.empty()) g[0][i] = *s.begin();
		else g[0][i] = i;
	}
	
//	cerr << "okay" << '\n';

//	for(int i = 1 ; i <= n ; i++) cout << f[0][i] << ' ' << g[0][i] << '\n';
	
	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]), st1[j - 1].update(1, 1, n, i, g[j - 1][i]);
		if(j > 17) break;
		
		for(int i = 1 ; i <= n ; i++)
		{
			int nxt = f[j - 1][i];
			int nxt1 = g[j - 1][i];
			
			f[j][i] = st[j - 1].get(1, 1, n, nxt1, nxt);
			g[j][i] = st1[j - 1].get(1, 1, n, nxt1, nxt);
			
//			cout << j << ' ' << i << ' ' << f[j][i] << ' ' << g[j][i] << '\n';
		}
		
//		cout << '\n';
	}
	
	
	for(int i = 1 ; i <= q ;  i++)
	{
		int l = t[i].l, r = t[i].r;
//		if(l < r)
//		{
//			int ans = 0;
	
			int cnt = 0;
			
			int L = l, R = l;
			
			for(int i = 17 ; i >= 0 ; i--)
			{
				int nwL = 1, nwR = n;
				
				if(cnt == 0)
				{
					nwL = g[i][L];
					nwR = f[i][R];
				}
				else 
				{
					nwL = st1[i].get(1, 1, n, L, R);
					nwR = st[i].get(1, 1, n, L, R);
				}
				

				
				if(!(nwL <= r && r <= nwR)) cnt |= (1 << i), L = nwL, R = nwR;
			}
			
			if(cnt == (1 << 18) - 1) ans[i] = -1;
			else ans[i] = cnt + 1;
			
//			cout << l << ' ' << r << '\n';
//			
//			for(int x = 1 ; x <= 10 ; x++) cout << lift(l, x) <<  ' '; cout << '\n';
// 		}
	}
}

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 <= 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: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13