oj.uz

Submission #847504

# Submission time Handle Problem Language Result Execution time Memory
847504 2023-09-09T18:32:35 Z _Avocado_ Railway Trip 2 (JOI22_ho_t4) C++14
27 / 100
 2000 ms 217552 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)*4;

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;
	
	for(int i = 0; i<=lg; ++i){
		for(int j = 0; j<MAX_N; ++j){
			seg_f[i][j] = 0;
			seg_b[i][j] = INF;
		}
	}
	
	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 34 ms 163408 KB Output is correct
2 Correct 22 ms 163416 KB Output is correct
3 Correct 23 ms 163416 KB Output is correct
4 Correct 23 ms 163420 KB Output is correct
5 Correct 24 ms 163412 KB Output is correct
6 Correct 23 ms 163420 KB Output is correct
7 Correct 23 ms 163364 KB Output is correct
8 Correct 22 ms 163408 KB Output is correct
9 Correct 23 ms 163412 KB Output is correct
10 Correct 21 ms 163124 KB Output is correct
11 Correct 23 ms 163420 KB Output is correct
12 Correct 23 ms 163420 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 163408 KB Output is correct
2 Correct 22 ms 163416 KB Output is correct
3 Correct 23 ms 163416 KB Output is correct
4 Correct 23 ms 163420 KB Output is correct
5 Correct 24 ms 163412 KB Output is correct
6 Correct 23 ms 163420 KB Output is correct
7 Correct 23 ms 163364 KB Output is correct
8 Correct 22 ms 163408 KB Output is correct
9 Correct 23 ms 163412 KB Output is correct
10 Correct 21 ms 163124 KB Output is correct
11 Correct 23 ms 163420 KB Output is correct
12 Correct 23 ms 163420 KB Output is correct
13 Correct 46 ms 164436 KB Output is correct
14 Correct 43 ms 164176 KB Output is correct
15 Correct 39 ms 164188 KB Output is correct
16 Correct 37 ms 164176 KB Output is correct
17 Correct 43 ms 164384 KB Output is correct
18 Correct 37 ms 164188 KB Output is correct
19 Correct 35 ms 164188 KB Output is correct
20 Correct 37 ms 164188 KB Output is correct
21 Correct 36 ms 164172 KB Output is correct
22 Correct 36 ms 164188 KB Output is correct
23 Correct 44 ms 164176 KB Output is correct
24 Correct 46 ms 164400 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1506 ms 217304 KB Output is correct
2 Correct 1485 ms 217296 KB Output is correct
3 Correct 1568 ms 217300 KB Output is correct
4 Correct 1432 ms 217424 KB Output is correct
5 Correct 964 ms 217428 KB Output is correct
6 Correct 1433 ms 217296 KB Output is correct
7 Correct 1291 ms 217308 KB Output is correct
8 Correct 1177 ms 216768 KB Output is correct
9 Correct 1198 ms 217300 KB Output is correct
10 Correct 1378 ms 217428 KB Output is correct
11 Correct 1368 ms 217304 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1895 ms 217412 KB Output is correct
2 Correct 1498 ms 217428 KB Output is correct
3 Execution timed out 2012 ms 217432 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1240 ms 217308 KB Output is correct
2 Execution timed out 2045 ms 217552 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 163408 KB Output is correct
2 Correct 22 ms 163416 KB Output is correct
3 Correct 23 ms 163416 KB Output is correct
4 Correct 23 ms 163420 KB Output is correct
5 Correct 24 ms 163412 KB Output is correct
6 Correct 23 ms 163420 KB Output is correct
7 Correct 23 ms 163364 KB Output is correct
8 Correct 22 ms 163408 KB Output is correct
9 Correct 23 ms 163412 KB Output is correct
10 Correct 21 ms 163124 KB Output is correct
11 Correct 23 ms 163420 KB Output is correct
12 Correct 23 ms 163420 KB Output is correct
13 Correct 46 ms 164436 KB Output is correct
14 Correct 43 ms 164176 KB Output is correct
15 Correct 39 ms 164188 KB Output is correct
16 Correct 37 ms 164176 KB Output is correct
17 Correct 43 ms 164384 KB Output is correct
18 Correct 37 ms 164188 KB Output is correct
19 Correct 35 ms 164188 KB Output is correct
20 Correct 37 ms 164188 KB Output is correct
21 Correct 36 ms 164172 KB Output is correct
22 Correct 36 ms 164188 KB Output is correct
23 Correct 44 ms 164176 KB Output is correct
24 Correct 46 ms 164400 KB Output is correct
25 Correct 1506 ms 217304 KB Output is correct
26 Correct 1485 ms 217296 KB Output is correct
27 Correct 1568 ms 217300 KB Output is correct
28 Correct 1432 ms 217424 KB Output is correct
29 Correct 964 ms 217428 KB Output is correct
30 Correct 1433 ms 217296 KB Output is correct
31 Correct 1291 ms 217308 KB Output is correct
32 Correct 1177 ms 216768 KB Output is correct
33 Correct 1198 ms 217300 KB Output is correct
34 Correct 1378 ms 217428 KB Output is correct
35 Correct 1368 ms 217304 KB Output is correct
36 Correct 1895 ms 217412 KB Output is correct
37 Correct 1498 ms 217428 KB Output is correct
38 Execution timed out 2012 ms 217432 KB Time limit exceeded
39 Halted 0 ms 0 KB -