제출 #1284761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284761		thuhienne	Escape Route 2 (JOI24_escape2)	C++20	23 / 100	244 ms	31156 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);
		}
		
		// Gi? s? flight[i] ban d?u là vector<pair<int,int>> {depart, arrive} cho city i
		auto &v = flight[i];
		
		// 1) Sort theo depart asc, arrive asc
		sort(v.begin(), v.end());
		
		// 2) G?p cùng depart, gi? arrival nh? nh?t
		vector<pair<int,int>> w;
		w.reserve(v.size());
		for (size_t p = 0; p < v.size(); ) {
		    size_t q = p;
		    int mind = v[p].second;
		    while (q < v.size() && v[q].first == v[p].first) {
		        mind = min(mind, v[q].second);
		        ++q;
		    }
		    w.push_back({v[p].first, mind});
		    p = q;
		}
		
		// 3) Suffix-min prune (gi? nh?ng chuy?n làm gi?m arrival khi di ngu?c)
		vector<pair<int,int>> opt;
		opt.reserve(w.size());
		int best = INT_MAX;
		for (int k = (int)w.size() - 1; k >= 0; --k) {
		    if (w[k].second >= best) continue; // b? th?ng tr? b?i suffix
		    best = w[k].second;
		    opt.push_back(w[k]);
		}
		reverse(opt.begin(), opt.end());
		
		// K?t qu? cu?i cùng
		flight[i].swap(opt);
		
		// (Sau dó fill position[i] nhu tru?c)
		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();
	
}

컴파일 시 표준 에러 (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