Submission #1284757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284757		thuhienne	Escape Route 2 (JOI24_escape2)	C++20	23 / 100	268 ms	31096 KiB

Main

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

using ll = long long;

#define re exit(0);
#define thuhien ""

const int LOG = 17;

int n,t;
vector <pair <int,int>> flight[100009];
vector <int> position[100009];

int cnt;
pair <int,int> plane[100009];
ll up[100009][LOG + 1];

int belong[100009];

ll nextday(ll day) {
	return 1ll*(day/t + 1)*t;
}

bool intersect(pair <int,int> a,pair <int,int> b) {
	if (a.first > b.first) swap(a,b);
	return !(a.first < b.first && a.second < b.second);
}

ll move(int l,int r,int currflight,int LOG) {
	ll res = 0;
	for (;;LOG--) if (l + (1 << LOG) - 1 <= r) break;
	int next = l + (1 << LOG) - 1;
	
	if (next == r) {
		return up[currflight][LOG];
	}
	
	res = up[currflight][LOG];
	
	int nextflight = lower_bound(flight[next].begin(),flight[next].end(),make_pair((int)(res % t),-1)) - flight[next].begin();

	if (nextflight != flight[next].size()) return res - res % t + move(next,r,position[next][nextflight],LOG);
	return nextday(res) + move(next,r,position[next][0],LOG);
}

void solve() {
	int l,r;cin >> l >> r;
	int currflight = position[l][0];
	cout << move(l,r,currflight,LOG) - flight[l][0].first << '\n';
}

int main() {
  ios_base::sync_with_stdio(0);cin.tie(nullptr);
	if (fopen(thuhien".inp","r")) {
		freopen(thuhien".inp","r",stdin);
		freopen(thuhien".out","w",stdout);
	}

	cin >> n >> t;
	for (int i = 1;i < n;i++) {
		int num;cin >> num;
		for (int j = 1;j <= num;j++) {
			pair <int,int> a;cin >> a.first >> a.second;
			flight[i].push_back(a);
		}
		
		sort(flight[i].begin(),flight[i].end(),[] (pair <int,int> a,pair <int,int> b) {
			if (a.first != b.first) return a.first < b.first;
			return a.second > b.second;
		});
		vector <pair <int,int>> temp;
		
		for (auto x : flight[i]) {
			while (temp.size() && intersect(x,temp.back())) temp.pop_back();
			temp.push_back(x);
		}
		
		flight[i] = temp;
		
		for (auto x : flight[i]) {
			cnt++;
			plane[cnt] = x;
			belong[cnt] = i;
			position[i].push_back(cnt);
		}
	}
	
//	for (int i = 1;i < n;i++) {
//		cout << "CITY: " << i << '\n';
//		for (auto x : position[i]) cout << x << '\n';
//	}
	
	//di tu i -> i + 1 mat min la bn
	for (int i = 1;i <= cnt;i++) {
		up[i][1] = plane[i].second;
	}
	for (int j = 2;j <= LOG;j++) {
		for (int i = 1;i <= cnt && belong[i] + (1 << j) - 1 <= n;i++) {
			int mid = belong[i] + (1 << (j - 1)) - 1,r = mid + 1;
			
			//mid -> r
			ll nexttime = up[i][j - 1];
			int nextflight = lower_bound(flight[mid].begin(),flight[mid].end(),make_pair((int)(nexttime % t),-1)) - flight[mid].begin();
			
			if (nextflight != flight[mid].size()) nexttime = nexttime - nexttime % t + flight[mid][nextflight].second;
			else nexttime = nextday(nexttime) + flight[mid][0].second;
			
			//xem bat chuyen nao cua r
			nextflight = lower_bound(flight[r].begin(),flight[r].end(),make_pair((int)(nexttime % t),-1)) - flight[r].begin();
			if (nextflight != flight[r].size()) up[i][j] = nexttime - nexttime % t + up[ position[r][nextflight] ][j - 1];
			else up[i][j] = nextday(nexttime) + up[ position[r][0] ][j - 1];
			
		}
	}
	
	int q;cin >> q;while (q--) solve();
	
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:56:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |                 freopen(thuhien".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:57:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |                 freopen(thuhien".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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