oj.uz

Submission #902023

# Submission time Handle Problem Language Result Execution time Memory
902023 2024-01-10T05:29:12 Z LCJLY Railway Trip 2 (JOI22_ho_t4) C++14
52 / 100
 2000 ms 313756 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[18];

void solve(){	
	int n,k;
	cin >> n >> k;
	int m;
	cin >> m;
	
	for(int x=0;x<18;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[18][n+5];
	for(int bit=0;bit<18;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=17;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=17;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 1368 KB Output is correct
2 Correct 3 ms 1368 KB Output is correct
3 Correct 3 ms 1372 KB Output is correct
4 Correct 3 ms 1368 KB Output is correct
5 Correct 3 ms 1372 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 2 ms 1372 KB Output is correct
9 Correct 3 ms 1372 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 3 ms 1372 KB Output is correct
12 Correct 2 ms 1396 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1368 KB Output is correct
2 Correct 3 ms 1368 KB Output is correct
3 Correct 3 ms 1372 KB Output is correct
4 Correct 3 ms 1368 KB Output is correct
5 Correct 3 ms 1372 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 2 ms 1372 KB Output is correct
9 Correct 3 ms 1372 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 3 ms 1372 KB Output is correct
12 Correct 2 ms 1396 KB Output is correct
13 Correct 23 ms 6492 KB Output is correct
14 Correct 21 ms 6492 KB Output is correct
15 Correct 14 ms 6492 KB Output is correct
16 Correct 23 ms 6664 KB Output is correct
17 Correct 19 ms 6668 KB Output is correct
18 Correct 19 ms 6672 KB Output is correct
19 Correct 19 ms 6236 KB Output is correct
20 Correct 19 ms 6492 KB Output is correct
21 Correct 16 ms 6492 KB Output is correct
22 Correct 21 ms 6492 KB Output is correct
23 Correct 20 ms 6488 KB Output is correct
24 Correct 18 ms 6672 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1016 ms 310608 KB Output is correct
2 Correct 1016 ms 310544 KB Output is correct
3 Correct 1073 ms 310472 KB Output is correct
4 Correct 977 ms 310276 KB Output is correct
5 Correct 1138 ms 310440 KB Output is correct
6 Correct 1043 ms 310608 KB Output is correct
7 Correct 1284 ms 310424 KB Output is correct
8 Correct 1190 ms 307324 KB Output is correct
9 Correct 1125 ms 310612 KB Output is correct
10 Correct 1097 ms 310608 KB Output is correct
11 Correct 1042 ms 310368 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1884 ms 310632 KB Output is correct
2 Correct 1485 ms 313224 KB Output is correct
3 Correct 1674 ms 312328 KB Output is correct
4 Correct 1578 ms 313092 KB Output is correct
5 Correct 1500 ms 310128 KB Output is correct
6 Correct 1411 ms 313224 KB Output is correct
7 Correct 1608 ms 313756 KB Output is correct
8 Correct 1772 ms 313728 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2037 ms 310936 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 1368 KB Output is correct
2 Correct 3 ms 1368 KB Output is correct
3 Correct 3 ms 1372 KB Output is correct
4 Correct 3 ms 1368 KB Output is correct
5 Correct 3 ms 1372 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 2 ms 1372 KB Output is correct
9 Correct 3 ms 1372 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 3 ms 1372 KB Output is correct
12 Correct 2 ms 1396 KB Output is correct
13 Correct 23 ms 6492 KB Output is correct
14 Correct 21 ms 6492 KB Output is correct
15 Correct 14 ms 6492 KB Output is correct
16 Correct 23 ms 6664 KB Output is correct
17 Correct 19 ms 6668 KB Output is correct
18 Correct 19 ms 6672 KB Output is correct
19 Correct 19 ms 6236 KB Output is correct
20 Correct 19 ms 6492 KB Output is correct
21 Correct 16 ms 6492 KB Output is correct
22 Correct 21 ms 6492 KB Output is correct
23 Correct 20 ms 6488 KB Output is correct
24 Correct 18 ms 6672 KB Output is correct
25 Correct 1016 ms 310608 KB Output is correct
26 Correct 1016 ms 310544 KB Output is correct
27 Correct 1073 ms 310472 KB Output is correct
28 Correct 977 ms 310276 KB Output is correct
29 Correct 1138 ms 310440 KB Output is correct
30 Correct 1043 ms 310608 KB Output is correct
31 Correct 1284 ms 310424 KB Output is correct
32 Correct 1190 ms 307324 KB Output is correct
33 Correct 1125 ms 310612 KB Output is correct
34 Correct 1097 ms 310608 KB Output is correct
35 Correct 1042 ms 310368 KB Output is correct
36 Correct 1884 ms 310632 KB Output is correct
37 Correct 1485 ms 313224 KB Output is correct
38 Correct 1674 ms 312328 KB Output is correct
39 Correct 1578 ms 313092 KB Output is correct
40 Correct 1500 ms 310128 KB Output is correct
41 Correct 1411 ms 313224 KB Output is correct
42 Correct 1608 ms 313756 KB Output is correct
43 Correct 1772 ms 313728 KB Output is correct
44 Execution timed out 2037 ms 310936 KB Time limit exceeded
45 Halted 0 ms 0 KB -