oj.uz

답안 #1038923

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1038923 2024-07-30T09:25:17 Z Unforgettablepl Escape Route 2 (JOI24_escape2) C++17
0 / 100
 470 ms 274084 KB 
#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 get = [&](int x,int target){
		int ans = 0;
		for(int bit=0;bit<17;bit++)if(target&(1<<bit)){
			ans+=liftcost[x][bit];
			x=lift[x][bit];
		}
		return ans-finalrangescost[x];
	};
	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';
	}
}

Compilation message

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
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 42 ms 4484 KB Output is correct
3 Incorrect 74 ms 9444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 42 ms 4484 KB Output is correct
3 Incorrect 74 ms 9444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 42 ms 4484 KB Output is correct
3 Incorrect 74 ms 9444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 42 ms 4484 KB Output is correct
3 Incorrect 74 ms 9444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 206 ms 39072 KB Output is correct
4 Correct 196 ms 38816 KB Output is correct
5 Correct 470 ms 38556 KB Output is correct
6 Correct 188 ms 38560 KB Output is correct
7 Correct 185 ms 38788 KB Output is correct
8 Correct 137 ms 21684 KB Output is correct
9 Correct 195 ms 39328 KB Output is correct
10 Correct 47 ms 21412 KB Output is correct
11 Incorrect 352 ms 274084 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 42 ms 4484 KB Output is correct
3 Incorrect 74 ms 9444 KB Output isn't correct
4 Halted 0 ms 0 KB -