Submission #847494

#	Time	Username	Problem	Language	Result	Execution time	Memory
847494		_Avocado_	Railway Trip 2 (JOI22_ho_t4)	C++14	27 / 100	2063 ms	220316 KiB

Main

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

const int INF = 1e9;
const int lg = 25;

void paste(int ql, int qr, int v, int pos, int l, int r, int op, auto&seg){
	if(l > qr || r < ql) return;
	if(l >= ql && r <= qr){
		if(op) seg[pos] = max(seg[pos], v);
		else seg[pos] = min(seg[pos], v);
		return;
	}
	paste(ql, qr, v, pos*2, l, (l+r)/2, op, seg);
	paste(ql, qr, v, pos*2+1, (l+r)/2+1, r, op, seg);
}

vector<int>beg_range_f, beg_range_b;

void walk_down(int pos, int l, int r, int op, auto&seg, auto&beg_range){
	if(l == r){
		if(op) beg_range[l] = max(seg[pos], l);
		else beg_range[l] = min(seg[pos], l);
		return;
	}
	if(op){
		seg[pos*2] = max(seg[pos*2], seg[pos]);
		seg[pos*2+1] = max(seg[pos*2+1], seg[pos]);
	}
	else{
		seg[pos*2] = min(seg[pos*2], seg[pos]);
		seg[pos*2+1] = min(seg[pos*2+1], seg[pos]);
	}
	
	walk_down(pos*2, l, (l+r)/2, op, seg, beg_range);
	walk_down(pos*2+1, (l+r)/2+1, r, op, seg, beg_range);
}

void update(int k, int v, int pos, int l, int r, int op, auto&seg){
	if(l == r){
		seg[pos] = v;
		return;
	}
	
	if(k <= (l+r)/2) update(k, v, pos*2, l, (l+r)/2, op, seg);
	else update(k, v, pos*2+1, (l+r)/2+1, r, op, seg);
	
	if(op) seg[pos] = max(seg[pos*2], seg[pos*2+1]);
	else seg[pos] = min(seg[pos*2], seg[pos*2+1]);
}

int query(int ql, int qr, int pos, int l, int r, int op, auto&seg){
	if(l > qr || r < ql || ql > qr){
		if(op) return 0;
		return INF;
	}
	if(l >= ql && r <= qr) return seg[pos];
	if(op) return max(query(ql, qr, pos*2, l, (l+r)/2, op, seg), query(ql, qr, pos*2+1, (l+r)/2+1, r, op, seg));
	return min(query(ql, qr, pos*2, l, (l+r)/2, op, seg), query(ql, qr, pos*2+1, (l+r)/2+1, r, op, seg));
}

void build(int pos, int l, int r, int op, auto&val, auto&seg){
	if(l == r){
		seg[pos] = val[l];
		return;
	}
	
	build(pos*2, l, (l+r)/2, op, val, seg);
	build(pos*2+1, (l+r)/2+1, r, op, val, seg);
	
	if(op) seg[pos] = max(seg[pos*2], seg[pos*2+1]);
	else seg[pos] = min(seg[pos*2], seg[pos*2+1]);
}
	

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	
	int n, k, m; cin>>n>>k>>m;
	
	++n;
	
	vector<int>beg_tree_f(n*4, 0);
	vector<int>beg_tree_b(n*4, INF);
	
	for(int i = 0; i<m; ++i){
		int a, b; cin>>a>>b;
		if(a < b){
			int end = min(a+k-1, n);
			paste(a, end, b, 1, 0, n-1, 1, beg_tree_f);
		}
		else{
			int start = max(a-k+1, (int)1);
			paste(start, a, b, 1, 0, n-1, 0, beg_tree_b);
		}
	}
	
	beg_range_f.assign(n, 0);
	beg_range_b.assign(n, 0);
	
	vector<vector<int>>seg_f, seg_b;
	seg_f.assign(lg+1, vector<int>(n*4, 0));
	seg_b.assign(lg+1, vector<int>(n*4, INF));
	
	walk_down(1, 0, n-1, 1, beg_tree_f, beg_range_f);
	walk_down(1, 0, n-1, 0, beg_tree_b, beg_range_b);
	
	vector<int>range_f = beg_range_f;
	vector<int>range_b = beg_range_b;
	
	build(1, 0, n-1, 1, range_f, seg_f[0]);
	build(1, 0, n-1, 0, range_b, seg_b[0]);
	
	/*
	for(auto u: range_f) cout<<u<<" ";
	cout<<endl;
	
	for(auto u: range_b) cout<<u<<" ";
	cout<<endl;
	*/
	
	vector<vector<pair<int, int>>>up(n, vector<pair<int, int>>(lg+1));
	
	for(int i = 1; i<n; ++i) up[i][0] = {range_b[i], range_f[i]};
	
	for(int i = 1; i<=lg; ++i){
		for(int j = 1; j<n; ++j){
			int l = range_b[j];
			int r = range_f[j];
			
			int next_l = query(l, r, 1, 0, n-1, 0, seg_b[i-1]);
			int next_r = query(l, r, 1, 0, n-1, 1, seg_f[i-1]);
			
			up[j][i] = {next_l, next_r};
			
			range_b[j] = next_l;
			range_f[j] = next_r;
			
			update(j, next_l, 1, 0, n-1, 0, seg_b[i]);
			update(j, next_r, 1, 0, n-1, 1, seg_f[i]);
		}
	}
			
	int q; cin>>q;
	
	for(int i = 0; i<q; ++i){
		int a, b; cin>>a>>b;
		
		int ans = 0;
		int op = 0;
		
		if(a < b){
			if(up[a][lg].second < b){
				cout<<-1<<'\n';
				continue;
			}
			
			op = 1;
		}
		else{
			if(up[a][lg].first > b){
				cout<<-1<<'\n';
				continue;
			}
		}
			
		int range = 0;
		for(int j = lg; j>=0; --j){
			if(op){
				if(up[a][j].second < b){
					range = j;
					ans += (1<<j);
					break;
				}
			}
			else{
				if(up[a][j].first > b){
					range = j;
					ans += (1<<j);
					break;
				}
			}
		}
		
		int cur_l = up[a][range].first;
		int cur_r = up[a][range].second;
		
		for(int j = range-1; j>=0; --j){
			int maxi = query(cur_l, cur_r, 1, 0, n-1, 1, seg_f[j]);
			int mini = query(cur_l, cur_r, 1, 0, n-1, 0, seg_b[j]);
			
			if((op && maxi < b) || (!op && mini > b)){
				cur_l = mini;
				cur_r = maxi;
				ans += (1<<j);
			}	
		}
		
		cout<<ans+1<<'\n';
	}
		

	cout<<'\n';
}

Compilation message (stderr)

Main.cpp:8:66: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    8 | void paste(int ql, int qr, int v, int pos, int l, int r, int op, auto&seg){
      |                                                                  ^~~~
Main.cpp:21:47: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   21 | void walk_down(int pos, int l, int r, int op, auto&seg, auto&beg_range){
      |                                               ^~~~
Main.cpp:21:57: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   21 | void walk_down(int pos, int l, int r, int op, auto&seg, auto&beg_range){
      |                                                         ^~~~
Main.cpp:40:58: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   40 | void update(int k, int v, int pos, int l, int r, int op, auto&seg){
      |                                                          ^~~~
Main.cpp:53:58: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   53 | int query(int ql, int qr, int pos, int l, int r, int op, auto&seg){
      |                                                          ^~~~
Main.cpp:63:43: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   63 | void build(int pos, int l, int r, int op, auto&val, auto&seg){
      |                                           ^~~~
Main.cpp:63:53: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   63 | void build(int pos, int l, int r, int op, auto&val, auto&seg){
      |                                                     ^~~~

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