Submission #1189672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189672		mertbbm	Escape Route 2 (JOI24_escape2)	C++20	23 / 100	243 ms	50108 KiB

Main

#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:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<int,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

int two[22][100005];
int dp[22][100005];
int offset[100005];
vector<pii>adj[100005];
const int blk=250;

void solve(){
	int n,k;
	cin >> n >> k;
	
	vector<pii>storage[n+5];
	int cur=0;
	for(int x=1;x<n;x++){
		int m;
		cin >> m;
		int temp,temp2;
		for(int y=0;y<m;y++){
			cin >> temp >> temp2;
			storage[x].push_back({temp,temp2});
		}
		sort(storage[x].begin(),storage[x].end());
		vector<pii>hold;
		int lst=1e15;
		for(int y=storage[x].size()-1;y>=0;y--){
			if(storage[x][y].second<lst){
				hold.push_back(storage[x][y]);
				lst=storage[x][y].second;
			}
		}
		storage[x]=hold;
		sort(storage[x].begin(),storage[x].end());
		offset[x]=cur;
		cur+=storage[x].size();
	}
	
	//build edges
	memset(two,-1,sizeof(two));
	for(int x=1;x<n-1;x++){
		int ptr=0;
		int index=0;
		for(auto it:storage[x]){
			while(ptr<(int)storage[x+1].size()&&storage[x+1][ptr].first<it.second) ptr++;
			if(ptr!=(int)storage[x+1].size()){
				two[0][offset[x]+index]=offset[x+1]+ptr;
				//show2(a,offset[x]+index,b,offset[x+1]+ptr);
				dp[0][offset[x]+index]=storage[x+1][ptr].second-it.second;
				adj[offset[x]+index].push_back({offset[x+1]+ptr,storage[x+1][ptr].second-it.second});
			}
			else{
				//show2(a,offset[x]+index,b,offset[x+1]);
				two[0][offset[x]+index]=offset[x+1];
				dp[0][offset[x]+index]=storage[x+1][0].second-it.second+k;
				adj[offset[x]+index].push_back({offset[x+1]+ptr,storage[x+1][0].second-it.second+k});
			}
			index++;
		}
	}
	
	//2k decomp
	for(int x=n;x>=0;x--){
		for(int y=0;y<20;y++){
			if(two[y][x]==-1) continue;
			two[y+1][x]=two[y][two[y][x]];
			dp[y+1][x]=dp[y][x]+dp[y][two[y][x]];
		}
	}
	
	//brute force
	vector<int>precompute[n+5];
	for(int x=1;x<=n;x++){
		if(storage[x].size()<=blk) continue;
		int dist[100005];
		precompute[x].resize(n,-1);
		memset(dist,0,sizeof(dist));
		queue<int>q;
		for(int y=0;y<(int)storage[x].size();y++){
			if(dist[offset[x]]+y!=-1&&dist[offset[x]+y]<=(storage[x][y].second-storage[x][y].first)) continue;
			dist[offset[x]+y]=(storage[x][y].second-storage[x][y].first);
		}
		
		for(int y=0;y<=n+2;y++){
			if(dist[y]==-1) continue;
			for(auto it:adj[y]){
				int nd=dist[y]+it.second;
				if(dist[it.first]!=-1&&dist[it.first]<=nd) continue;
				dist[it.first]=nd;
			}
			int index=upper_bound(offset+1,offset+n,y)-offset;
			if(precompute[x][index]!=-1&&precompute[x][index]<=dist[y]) continue;
			precompute[x][index]=dist[y];
		}
	}
	
	//for(int x=1;x<=n;x++){
		//show2(x,x,offset[x],offset[x]);
	//}
	
	int q;
	cin >> q;
	int l,r;
	for(int x=0;x<q;x++){
		cin >> l >> r;
		if(storage[l].size()>blk){
			r--;
			cout << precompute[l][r] << "\n";
		}
		else{
			r--;
			int index=0;
			int best=1e18;
			for(auto it:storage[l]){
				//binary lifting
				//show2(it.first,it.first,it.second,it.second);
				int cur=index+offset[l];
				int counter=(it.second-it.first);
				//show(cur,cur);
				//show(offset[r],offset[r]);
				for(int y=19;y>=0;y--){
					//cout << y << " " << cur << " " << two[y][cur] << endl;
					if(two[y][cur]==-1) continue;
					if(two[y][cur]<offset[r]){
						counter+=dp[y][cur];
						cur=two[y][cur];
					}
				}
				//show(cur,cur);
				if(l!=r)counter+=dp[0][cur];
				best=min(best,counter);
			}
			cout << best << "\n";
		}
	}
		
	
}	
																   
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 8
• Subtask 3: 17 / 17
• Subtask 4: 0 / 23
• Subtask 5: 0 / 36
• Subtask 6: 0 / 10