oj.uz

Submission #847499

# Submission time Handle Problem Language Result Execution time Memory
847499 2023-09-09T18:27:17 Z _Avocado_ Railway Trip 2 (JOI22_ho_t4) C++14
16 / 100
 1288 ms 192692 KB 
#include <bits/stdc++.h>
#define int int64_t
using namespace std;

const int INF = 1e9;
const int lg = 25;
const int MAX_N = 1e5+5;

int seg_f[lg+1][MAX_N];
int seg_b[lg+1][MAX_N];

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);
	
	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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 39512 KB Output is correct
2 Correct 7 ms 39772 KB Output is correct
3 Correct 6 ms 39616 KB Output is correct
4 Correct 6 ms 39516 KB Output is correct
5 Correct 7 ms 39516 KB Output is correct
6 Correct 6 ms 39516 KB Output is correct
7 Correct 7 ms 39516 KB Output is correct
8 Correct 6 ms 39584 KB Output is correct
9 Correct 7 ms 39512 KB Output is correct
10 Correct 4 ms 39424 KB Output is correct
11 Correct 6 ms 39516 KB Output is correct
12 Correct 6 ms 39516 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 39512 KB Output is correct
2 Correct 7 ms 39772 KB Output is correct
3 Correct 6 ms 39616 KB Output is correct
4 Correct 6 ms 39516 KB Output is correct
5 Correct 7 ms 39516 KB Output is correct
6 Correct 6 ms 39516 KB Output is correct
7 Correct 7 ms 39516 KB Output is correct
8 Correct 6 ms 39584 KB Output is correct
9 Correct 7 ms 39512 KB Output is correct
10 Correct 4 ms 39424 KB Output is correct
11 Correct 6 ms 39516 KB Output is correct
12 Correct 6 ms 39516 KB Output is correct
13 Correct 30 ms 40788 KB Output is correct
14 Correct 30 ms 40792 KB Output is correct
15 Correct 23 ms 40540 KB Output is correct
16 Correct 19 ms 40540 KB Output is correct
17 Correct 26 ms 40540 KB Output is correct
18 Correct 19 ms 40536 KB Output is correct
19 Correct 19 ms 40440 KB Output is correct
20 Correct 19 ms 40540 KB Output is correct
21 Correct 19 ms 40540 KB Output is correct
22 Correct 20 ms 40536 KB Output is correct
23 Correct 28 ms 40492 KB Output is correct
24 Correct 27 ms 40528 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 897 ms 192500 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1288 ms 192692 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 758 ms 192564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 39512 KB Output is correct
2 Correct 7 ms 39772 KB Output is correct
3 Correct 6 ms 39616 KB Output is correct
4 Correct 6 ms 39516 KB Output is correct
5 Correct 7 ms 39516 KB Output is correct
6 Correct 6 ms 39516 KB Output is correct
7 Correct 7 ms 39516 KB Output is correct
8 Correct 6 ms 39584 KB Output is correct
9 Correct 7 ms 39512 KB Output is correct
10 Correct 4 ms 39424 KB Output is correct
11 Correct 6 ms 39516 KB Output is correct
12 Correct 6 ms 39516 KB Output is correct
13 Correct 30 ms 40788 KB Output is correct
14 Correct 30 ms 40792 KB Output is correct
15 Correct 23 ms 40540 KB Output is correct
16 Correct 19 ms 40540 KB Output is correct
17 Correct 26 ms 40540 KB Output is correct
18 Correct 19 ms 40536 KB Output is correct
19 Correct 19 ms 40440 KB Output is correct
20 Correct 19 ms 40540 KB Output is correct
21 Correct 19 ms 40540 KB Output is correct
22 Correct 20 ms 40536 KB Output is correct
23 Correct 28 ms 40492 KB Output is correct
24 Correct 27 ms 40528 KB Output is correct
25 Runtime error 897 ms 192500 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -