제출 #1038928

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1038928		Unforgettablepl	Escape Route 2 (JOI24_escape2)	C++17	100 / 100	1733 ms	310176 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SQRT = 317;
const int INF = 1e18;


int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,T;
	cin >> n >> T;
	vector<vector<int>> lift(1,vector<int>(17));
	vector<vector<int>> liftcost(1,vector<int>(17));
	int c = 0;
	vector<vector<pair<int,int>>> pairers(n+1);
	vector<vector<int>> bestranges(n+1);
	vector<pair<int,int>> finalranges(1);
	vector<int> finalrangescost(1);
	for(int i=1;i<n;i++){
		int m;cin>>m;
		vector<pair<int,int>> ranges(m);
		for(auto&[b,a]:ranges)cin>>a>>b;
		sort(ranges.begin(),ranges.end());
		int last_start = -1;
		for(auto&[b,a]:ranges){
			if(a<=last_start)continue;
			last_start = a;
			int idx=++c;
			pairers[i].emplace_back(a,idx);
			lift.emplace_back(vector<int>(17));
			liftcost.emplace_back(vector<int>(17));
			liftcost[idx][0]=b-a;
			finalranges.emplace_back(a,b);
			finalrangescost.emplace_back(0);
		}
	}
	for(int i=1;i<n-1;i++){
		for(auto&[a,idx]:pairers[i]){
			int b = finalranges[idx].second;
			auto iter = lower_bound(pairers[i+1].begin(),pairers[i+1].end(),make_pair(b,0ll));
			if(iter==pairers[i+1].end()){
				finalrangescost[idx]=T-b+pairers[i+1].front().first;
				lift[idx][0]=pairers[i+1].front().second;
			} else {
				finalrangescost[idx]=(iter->first)-b;
				lift[idx][0]=iter->second;
			}
			liftcost[idx][0]+=finalrangescost[idx];
		}
	}
	for(int bit=1;bit<17;bit++){
		for(int i=1;i<=c;i++){
			lift[i][bit]=lift[lift[i][bit-1]][bit-1];
			liftcost[i][bit]=liftcost[lift[i][bit-1]][bit-1]+liftcost[i][bit-1];
		}
	}
	vector<vector<int>> bestanssqrt(n+1,vector<int>(SQRT+1,INF));
	for(int i=1;i<n;i++){
		vector<tuple<int,int,int>> options;
		for(auto&[a,idx]:pairers[i]){
			int currcost = finalranges[idx].second-finalranges[idx].first;
			int last_range = idx;
			for(int j=i+1;j<=min(n,i+SQRT);j++){
				bestanssqrt[i][j-i]=min(bestanssqrt[i][j-i],currcost);
				currcost+=finalrangescost[last_range];
				last_range = lift[last_range][0];
				currcost+=finalranges[last_range].second-finalranges[last_range].first;
			}
			options.emplace_back(last_range,currcost,idx);
		}
		options.emplace_back(0,0,0);
		sort(options.begin(),options.end());
		for(int j=1;j<options.size();j++){
			if(get<0>(options[j])!=get<0>(options[j-1]))bestranges[i].emplace_back(get<2>(options[j]));
		}
	}
	auto gett = [&](int x,int target){
		for(int bit=0;bit<17;bit++)if(target&(1<<bit))x=lift[x][bit];
		return x;
	};
	auto get = [&](int x,int target){
		int ans = -finalrangescost[gett(x,target-1)];
		for(int bit=0;bit<17;bit++)if(target&(1<<bit)){
			ans+=liftcost[x][bit];
			x=lift[x][bit];
		}
		return ans;
	};
	int q;
	cin >> q;
	for(int i=1;i<=q;i++){
		int l,r;cin>>l>>r;
		if(r-l<=SQRT){
			cout << bestanssqrt[l][r-l] << '\n';
			continue;
		}
		int ans = INF;
		for(int&j:bestranges[l]){
			ans=min(ans,get(j,r-l));
		}
		cout << ans << '\n';
	}
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int32_t main()':
Main.cpp:76:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for(int j=1;j<options.size();j++){
      |               ~^~~~~~~~~~~~~~~

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