oj.uz

Submission #902020

# Submission time Handle Problem Language Result Execution time Memory
902020 2024-01-10T05:27:51 Z LCJLY Railway Trip 2 (JOI22_ho_t4) C++14
27 / 100
 2000 ms 347764 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<long long,long long>pii;

inline pii combine(pii a, pii b){
	return {min(a.first,b.first),max(a.second,b.second)};
}

struct node{
	int s,e,m;
	node *l,*r;
	pii v; //mini maxi
	int lazyMin,lazyMax;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1){
		v={s,e};
		lazyMin=INT_MAX;
		lazyMax=INT_MIN;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			v=combine(l->v,r->v);
		}
	}
	
	void self_min(int x){
		v.first=min(v.first,x);
		lazyMin=min(lazyMin,x);
	}
	
	void self_max(int x){
		v.second=max(v.second,x);
		lazyMax=max(lazyMax,x);
	}
	
	void forceProp(){
		if(s==e) return;
		l->self_min(lazyMin); r->self_min(lazyMin);
		l->self_max(lazyMax); r->self_max(lazyMax);
	}
	
	void rangeUpd(int x, int y, pii c){
		if(x<=s&&y>=e){
			self_min(c.first);
			self_max(c.second);
			return;
		}
		forceProp();
		if(x<=m)l->rangeUpd(x,y,c);
		if(y>m)r->rangeUpd(x,y,c);
		v=combine(l->v,r->v);
	}
	
	pii query(int x, int y){
		if(x<=s&&y>=e){
			return v;
		}
		forceProp();
		if(y<=m)return l->query(x,y);
		if(x>m)return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
}*st[20];

void solve(){	
	int n,k;
	cin >> n >> k;
	int m;
	cin >> m;
	
	for(int x=0;x<20;x++){
		st[x]=new node(0,n+5);
	}
	
	int temp,temp2;
	for(int x=0;x<m;x++){
		cin >> temp >> temp2;
		if(temp<temp2){
			int hold=min(temp+k-1,temp2);
			st[0]->rangeUpd(temp,hold,{temp2,temp2});
		}
		else{
			int hold=max(temp-k+1,temp2);
			st[0]->rangeUpd(hold,temp,{temp2,temp2});
		}
	}
	
	pii two[20][n+5];
	for(int bit=0;bit<20;bit++){
		for(int x=0;x<=n;x++){
			if(bit==0){
				two[bit][x]=st[bit]->query(x,x);
			}
			else{
				two[bit][x]=st[bit-1]->query(two[bit-1][x].first,two[bit-1][x].second);
				st[bit]->rangeUpd(x,x,two[bit][x]);
				//show2(bit,bit,x,x);
				//show2(l,two[bit][x].first,r,two[bit][x].second);
				//show2(prev,two[bit-1][x].first,prev,two[bit-1][x].second);
			}
		}
	}
	
	int q;
	cin >> q;
	
	for(int x=0;x<q;x++){
		cin >> temp >> temp2;
		
		if(temp<temp2){
			int l=temp;
			int r=temp;
			
			int ans=0;
			for(int bit=19;bit>=0;bit--){
				pii hold=st[bit]->query(l,r);
				if(hold.second<temp2){
					ans+=1<<bit;
					l=hold.first;
					r=hold.second;
				}
			}
			
			if(st[0]->query(l,r).second<temp2){
				cout << -1 << "\n";
			}
			else{
				cout << ans+1 << "\n";
			}
		}
		else{
			int l=temp;
			int r=temp;
			
			int ans=0;
			for(int bit=19;bit>=0;bit--){
				pii hold=st[bit]->query(l,r);
				if(hold.first>temp2){
					ans+=1<<bit;
					l=hold.first;
					r=hold.second;
				}
			}
			
			if(st[0]->query(l,r).first>temp2){
				cout << -1 << "\n";
			}
			else{
				cout << ans+1 << "\n";
			}
		}
	}
}	
 
int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1372 KB Output is correct
2 Correct 3 ms 1372 KB Output is correct
3 Correct 2 ms 1372 KB Output is correct
4 Correct 3 ms 1372 KB Output is correct
5 Correct 3 ms 1372 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Correct 3 ms 1372 KB Output is correct
8 Correct 2 ms 1372 KB Output is correct
9 Correct 3 ms 1372 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 3 ms 1372 KB Output is correct
12 Correct 3 ms 1372 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1372 KB Output is correct
2 Correct 3 ms 1372 KB Output is correct
3 Correct 2 ms 1372 KB Output is correct
4 Correct 3 ms 1372 KB Output is correct
5 Correct 3 ms 1372 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Correct 3 ms 1372 KB Output is correct
8 Correct 2 ms 1372 KB Output is correct
9 Correct 3 ms 1372 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 3 ms 1372 KB Output is correct
12 Correct 3 ms 1372 KB Output is correct
13 Correct 26 ms 7380 KB Output is correct
14 Correct 23 ms 7256 KB Output is correct
15 Correct 16 ms 7260 KB Output is correct
16 Correct 25 ms 7260 KB Output is correct
17 Correct 22 ms 7260 KB Output is correct
18 Correct 21 ms 7260 KB Output is correct
19 Correct 24 ms 7116 KB Output is correct
20 Correct 22 ms 7260 KB Output is correct
21 Correct 20 ms 7260 KB Output is correct
22 Correct 28 ms 7260 KB Output is correct
23 Correct 23 ms 7260 KB Output is correct
24 Correct 19 ms 7400 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1171 ms 345812 KB Output is correct
2 Correct 1104 ms 345784 KB Output is correct
3 Correct 1330 ms 345972 KB Output is correct
4 Correct 1121 ms 345680 KB Output is correct
5 Correct 1242 ms 347172 KB Output is correct
6 Correct 1127 ms 347172 KB Output is correct
7 Correct 1353 ms 346672 KB Output is correct
8 Correct 1317 ms 342668 KB Output is correct
9 Correct 1257 ms 346024 KB Output is correct
10 Correct 1217 ms 347172 KB Output is correct
11 Correct 1210 ms 347172 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 346448 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 347764 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1372 KB Output is correct
2 Correct 3 ms 1372 KB Output is correct
3 Correct 2 ms 1372 KB Output is correct
4 Correct 3 ms 1372 KB Output is correct
5 Correct 3 ms 1372 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Correct 3 ms 1372 KB Output is correct
8 Correct 2 ms 1372 KB Output is correct
9 Correct 3 ms 1372 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 3 ms 1372 KB Output is correct
12 Correct 3 ms 1372 KB Output is correct
13 Correct 26 ms 7380 KB Output is correct
14 Correct 23 ms 7256 KB Output is correct
15 Correct 16 ms 7260 KB Output is correct
16 Correct 25 ms 7260 KB Output is correct
17 Correct 22 ms 7260 KB Output is correct
18 Correct 21 ms 7260 KB Output is correct
19 Correct 24 ms 7116 KB Output is correct
20 Correct 22 ms 7260 KB Output is correct
21 Correct 20 ms 7260 KB Output is correct
22 Correct 28 ms 7260 KB Output is correct
23 Correct 23 ms 7260 KB Output is correct
24 Correct 19 ms 7400 KB Output is correct
25 Correct 1171 ms 345812 KB Output is correct
26 Correct 1104 ms 345784 KB Output is correct
27 Correct 1330 ms 345972 KB Output is correct
28 Correct 1121 ms 345680 KB Output is correct
29 Correct 1242 ms 347172 KB Output is correct
30 Correct 1127 ms 347172 KB Output is correct
31 Correct 1353 ms 346672 KB Output is correct
32 Correct 1317 ms 342668 KB Output is correct
33 Correct 1257 ms 346024 KB Output is correct
34 Correct 1217 ms 347172 KB Output is correct
35 Correct 1210 ms 347172 KB Output is correct
36 Execution timed out 2029 ms 346448 KB Time limit exceeded
37 Halted 0 ms 0 KB -