oj.uz

Submission #531717

# Submission time Handle Problem Language Result Execution time Memory
531717 2022-03-01T10:21:30 Z errorgorn Railway Trip 2 (JOI22_ho_t4) C++17
100 / 100
 512 ms 70940 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct ST{ //sparse table
	int arr[100005][18];
	
	ST(vector<int> v){
		rep(x,0,sz(v)) arr[x][0]=v[x];
		
		int layer=1;
		int curr=1;
		
		while (curr<100005){
			rep(x,0,100005-curr){
				arr[x][layer]=max(arr[x+curr][layer-1],arr[x][layer-1]);
			}
			
			layer++;
			curr<<=1;
		}
	}
	
	int query(int i,int j){
		int len=31-__builtin_clz(j-i+1);
		return max(arr[i][len],arr[j-(1<<len)+1][len]);
	}
};

struct ST2{ //sparse table
	int arr[100005][18];
	
	ST2(vector<int> v){
		rep(x,0,sz(v)) arr[x][0]=v[x];
		
		int layer=1;
		int curr=1;
		
		while (curr<100005){
			rep(x,0,100005-curr){
				arr[x][layer]=min(arr[x+curr][layer-1],arr[x][layer-1]);
			}
			
			layer++;
			curr<<=1;
		}
	}
	
	int query(int i,int j){
		int len=31-__builtin_clz(j-i+1);
		return min(arr[i][len],arr[j-(1<<len)+1][len]);
	}
};

int n,m,k,q;
vector<ii> fwd;
vector<ii> bwd;

#define iii pair<ii,int>
set<iii> s;

void ins(int l,int r,int v){
	auto it=--s.lb({{l+1,-1},-1});
	
	while (it!=s.end() && (*it).fi.fi<=r){
		iii temp=(*it);
		it++;
		
		s.erase(temp);
		if (temp.fi.fi<l) s.insert({{temp.fi.fi,l-1},temp.se});
		if (r<temp.fi.se) s.insert({{r+1,temp.fi.se},temp.se});
	}
	
	s.insert({{l,r},v});
}

ii tkd[100005][18]; //points to the guy that can go the furthest (l,r)

vector<int> vl,vr;
ii conv(int l,int r,int layer){
	int l2,r2;
	int temp1,temp2;
	
	tie(temp1,temp2)={
		tkd[l][layer].fi,
		tkd[r][layer].fi
	};
	if (vl[temp1]<vl[temp2]) l2=temp1;
	else l2=temp2;
	
	tie(temp1,temp2)={
		tkd[l][layer].se,
		tkd[r][layer].se
	};
	if (vr[temp1]>vr[temp2]) r2=temp1;
	else r2=temp2;
	
	return {l2,r2};
}

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k>>m;
	
	int a,b;
	rep(x,0,m){
		cin>>a>>b;
		
		if (a<b) fwd.pub({a,b});
		else bwd.pub({b,a});
	}
	
	s.clear();
	rep(x,0,n+1) s.insert(iii(ii(x,x),x));
	sort(all(fwd),[](ii i,ii j){
		return i.se<j.se;
	});
	for (auto it:fwd) ins(it.fi,min(it.se,it.fi+k-1),it.se);
	for (auto it:s) rep(x,it.fi.fi,it.fi.se+1) vr.pub(it.se);
	ST R=ST(vr);
	
	s.clear();
	rep(x,0,n+1) s.insert(iii(ii(x,x),x));
	sort(all(bwd),[](ii i,ii j){
		return i.fi>j.fi;
	});
	for (auto it:bwd) ins(max(it.fi,it.se-k+1),it.se,it.fi);
	for (auto it:s) rep(x,it.fi.fi,it.fi.se+1) vl.pub(it.se);
	ST2 L=ST2(vl);
	
	//rep(x,1,n+1) cout<<vl[x]<<" "; cout<<endl;
	//rep(x,1,n+1) cout<<vr[x]<<" "; cout<<endl;
	
	rep(x,1,n+1){ //furthest right guy
		int lo=vl[x]-1,hi=vr[x],mi;
		int val=R.query(vl[x],vr[x]);
		
		while (hi-lo>1){
			mi=hi+lo>>1;
			if (R.query(vl[x],mi)!=val) lo=mi;
			else hi=mi;
		}
		
		tkd[x][0].se=hi;
	}
	rep(x,1,n+1){ //furthest left guy
		int lo=vl[x],hi=vr[x]+1,mi;
		int val=L.query(vl[x],vr[x]);
		
		while (hi-lo>1){
			mi=hi+lo>>1;
			if (L.query(mi,vr[x])!=val) hi=mi;
			else lo=mi;
		}
		
		tkd[x][0].fi=lo;
	}
	
	//rep(x,1,n+1) cout<<vl[x]<<" "; cout<<endl;
	//rep(x,1,n+1) cout<<vr[x]<<" "; cout<<endl;
	//rep(x,1,n+1) cout<<tkd[x][0].fi<<" "<<tkd[x][0].se<<endl;
	
	rep(x,1,18){
		rep(y,1,n+1){
			tkd[y][x]=conv(tkd[y][x-1].fi,tkd[y][x-1].se,x-1);
		}
	}
	
	cin>>q;
	while (q--){
		cin>>a>>b;
		
		int l=a,r=a;
		int ans=1;
		rep(x,18,0){
			int l2,r2;
			tie(l2,r2)=conv(l,r,x);
			
			if (b<vl[l2] || vr[r2]<b){
				ans+=(1<<x);
				l=l2;
				r=r2;
			}
		}
		
		if (b<vl[l] || vr[r]<b){
			tie(l,r)=conv(l,r,0);
			ans++;
		}
		if (b<vl[l] || vr[r]<b) ans=-1;
		
		cout<<ans<<endl;
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:160:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  160 |    mi=hi+lo>>1;
      |       ~~^~~
Main.cpp:172:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  172 |    mi=hi+lo>>1;
      |       ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 28612 KB Output is correct
2 Correct 44 ms 28528 KB Output is correct
3 Correct 43 ms 28524 KB Output is correct
4 Correct 41 ms 28612 KB Output is correct
5 Correct 43 ms 28552 KB Output is correct
6 Correct 47 ms 28572 KB Output is correct
7 Correct 50 ms 28536 KB Output is correct
8 Correct 48 ms 28500 KB Output is correct
9 Correct 46 ms 28540 KB Output is correct
10 Correct 41 ms 28492 KB Output is correct
11 Correct 43 ms 28504 KB Output is correct
12 Correct 48 ms 28532 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 28612 KB Output is correct
2 Correct 44 ms 28528 KB Output is correct
3 Correct 43 ms 28524 KB Output is correct
4 Correct 41 ms 28612 KB Output is correct
5 Correct 43 ms 28552 KB Output is correct
6 Correct 47 ms 28572 KB Output is correct
7 Correct 50 ms 28536 KB Output is correct
8 Correct 48 ms 28500 KB Output is correct
9 Correct 46 ms 28540 KB Output is correct
10 Correct 41 ms 28492 KB Output is correct
11 Correct 43 ms 28504 KB Output is correct
12 Correct 48 ms 28532 KB Output is correct
13 Correct 56 ms 29256 KB Output is correct
14 Correct 60 ms 29248 KB Output is correct
15 Correct 41 ms 29280 KB Output is correct
16 Correct 45 ms 29280 KB Output is correct
17 Correct 45 ms 29248 KB Output is correct
18 Correct 47 ms 29252 KB Output is correct
19 Correct 49 ms 29204 KB Output is correct
20 Correct 48 ms 29148 KB Output is correct
21 Correct 43 ms 29124 KB Output is correct
22 Correct 49 ms 29212 KB Output is correct
23 Correct 47 ms 29252 KB Output is correct
24 Correct 48 ms 29256 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 67720 KB Output is correct
2 Correct 202 ms 67652 KB Output is correct
3 Correct 227 ms 68096 KB Output is correct
4 Correct 229 ms 67480 KB Output is correct
5 Correct 319 ms 69260 KB Output is correct
6 Correct 286 ms 70940 KB Output is correct
7 Correct 270 ms 69028 KB Output is correct
8 Correct 245 ms 65264 KB Output is correct
9 Correct 282 ms 66592 KB Output is correct
10 Correct 369 ms 70864 KB Output is correct
11 Correct 443 ms 70920 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 66776 KB Output is correct
2 Correct 454 ms 69968 KB Output is correct
3 Correct 373 ms 68904 KB Output is correct
4 Correct 373 ms 68136 KB Output is correct
5 Correct 465 ms 67004 KB Output is correct
6 Correct 410 ms 67428 KB Output is correct
7 Correct 472 ms 68868 KB Output is correct
8 Correct 512 ms 69004 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 69104 KB Output is correct
2 Correct 346 ms 67388 KB Output is correct
3 Correct 363 ms 66676 KB Output is correct
4 Correct 364 ms 66204 KB Output is correct
5 Correct 248 ms 65844 KB Output is correct
6 Correct 295 ms 65720 KB Output is correct
7 Correct 324 ms 67444 KB Output is correct
8 Correct 54 ms 28516 KB Output is correct
9 Correct 53 ms 29288 KB Output is correct
10 Correct 378 ms 69084 KB Output is correct
11 Correct 416 ms 69040 KB Output is correct
12 Correct 438 ms 68876 KB Output is correct
13 Correct 432 ms 69084 KB Output is correct
14 Correct 42 ms 28536 KB Output is correct
15 Correct 54 ms 29216 KB Output is correct
16 Correct 294 ms 68868 KB Output is correct
17 Correct 432 ms 68944 KB Output is correct
18 Correct 424 ms 68932 KB Output is correct
19 Correct 467 ms 69020 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 28612 KB Output is correct
2 Correct 44 ms 28528 KB Output is correct
3 Correct 43 ms 28524 KB Output is correct
4 Correct 41 ms 28612 KB Output is correct
5 Correct 43 ms 28552 KB Output is correct
6 Correct 47 ms 28572 KB Output is correct
7 Correct 50 ms 28536 KB Output is correct
8 Correct 48 ms 28500 KB Output is correct
9 Correct 46 ms 28540 KB Output is correct
10 Correct 41 ms 28492 KB Output is correct
11 Correct 43 ms 28504 KB Output is correct
12 Correct 48 ms 28532 KB Output is correct
13 Correct 56 ms 29256 KB Output is correct
14 Correct 60 ms 29248 KB Output is correct
15 Correct 41 ms 29280 KB Output is correct
16 Correct 45 ms 29280 KB Output is correct
17 Correct 45 ms 29248 KB Output is correct
18 Correct 47 ms 29252 KB Output is correct
19 Correct 49 ms 29204 KB Output is correct
20 Correct 48 ms 29148 KB Output is correct
21 Correct 43 ms 29124 KB Output is correct
22 Correct 49 ms 29212 KB Output is correct
23 Correct 47 ms 29252 KB Output is correct
24 Correct 48 ms 29256 KB Output is correct
25 Correct 219 ms 67720 KB Output is correct
26 Correct 202 ms 67652 KB Output is correct
27 Correct 227 ms 68096 KB Output is correct
28 Correct 229 ms 67480 KB Output is correct
29 Correct 319 ms 69260 KB Output is correct
30 Correct 286 ms 70940 KB Output is correct
31 Correct 270 ms 69028 KB Output is correct
32 Correct 245 ms 65264 KB Output is correct
33 Correct 282 ms 66592 KB Output is correct
34 Correct 369 ms 70864 KB Output is correct
35 Correct 443 ms 70920 KB Output is correct
36 Correct 363 ms 66776 KB Output is correct
37 Correct 454 ms 69968 KB Output is correct
38 Correct 373 ms 68904 KB Output is correct
39 Correct 373 ms 68136 KB Output is correct
40 Correct 465 ms 67004 KB Output is correct
41 Correct 410 ms 67428 KB Output is correct
42 Correct 472 ms 68868 KB Output is correct
43 Correct 512 ms 69004 KB Output is correct
44 Correct 482 ms 69104 KB Output is correct
45 Correct 346 ms 67388 KB Output is correct
46 Correct 363 ms 66676 KB Output is correct
47 Correct 364 ms 66204 KB Output is correct
48 Correct 248 ms 65844 KB Output is correct
49 Correct 295 ms 65720 KB Output is correct
50 Correct 324 ms 67444 KB Output is correct
51 Correct 54 ms 28516 KB Output is correct
52 Correct 53 ms 29288 KB Output is correct
53 Correct 378 ms 69084 KB Output is correct
54 Correct 416 ms 69040 KB Output is correct
55 Correct 438 ms 68876 KB Output is correct
56 Correct 432 ms 69084 KB Output is correct
57 Correct 42 ms 28536 KB Output is correct
58 Correct 54 ms 29216 KB Output is correct
59 Correct 294 ms 68868 KB Output is correct
60 Correct 432 ms 68944 KB Output is correct
61 Correct 424 ms 68932 KB Output is correct
62 Correct 467 ms 69020 KB Output is correct
63 Correct 356 ms 66816 KB Output is correct
64 Correct 405 ms 67196 KB Output is correct
65 Correct 339 ms 66952 KB Output is correct
66 Correct 429 ms 67728 KB Output is correct
67 Correct 419 ms 68932 KB Output is correct
68 Correct 462 ms 66912 KB Output is correct
69 Correct 471 ms 67168 KB Output is correct
70 Correct 458 ms 68780 KB Output is correct
71 Correct 424 ms 68976 KB Output is correct