Submission #704765

#	Time	Username	Problem	Language	Result	Execution time	Memory
704765		dubabuba	Toll (BOI17_toll)	C++14	0 / 100	3072 ms	22628 KiB

toll

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

typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const int mxn = 3e5 + 10;
map<pii, int> mp;
int n, m, k, q;

bool inmap(pii p) {
	auto it = mp.find(p);
	return it != mp.end();
}

void pushmap(pii p, int val) {
	if(inmap(p)) return;
	mp[p] = val;
}

void build(int l, int r) {
	cout << "building: " << l << ' ' << r << '\n';
	if(r - l < 2) return;
	int m = (l + r) / 2;
	
	build(l, m);
	build(m, r);
	
	for(int L = 1; L <= k; L++)
	for(int R = 1; R <= k; R++)
	for(int M = 1; M <= k; M++) {
		int st = L + (l - 1) * k;
		int en = R + (r - 1) * k;
		int md = M + (m - 1) * k;
//		if(en > n) break;
		if(inmap(MP(st, md)) && inmap(MP(md, en))) {
			int sus = mp[MP(st, en)];
			int LL = mp[MP(st, md)];
			int RR = mp[MP(md, en)];
			if(sus == 0) mp[MP(st, en)] = LL + RR;
			else if(sus > LL + RR)
				mp[MP(st, en)] = LL + RR;
			cout << "l = " << l << ' ' << k << ' ' << L << ' ' << st << '\n';
			cout << "r = " << r << ' ' << k << ' ' << R << ' ' << en << '\n';
			cout << "    " << mp[MP(st, en)] << '\n';
		}
	}
}

int query(int l, int r) {
	int L = 1, R = n / k + 1;
	while(R - L > 1) {
		int M = (L + R) / 2, ret = INT_MAX;
		bool sus = 0;
		
		for(int t = 1; t <= k; t++) {
			int mid = t + (M - 1) * k;
			if(l <= mid && mid <= r) {
				sus = 1;
				if(inmap(MP(l, mid)) && inmap(MP(mid, r)))
					ret = min(ret, mp[MP(l, mid)] + mp[MP(mid, r)]);
			}
		}
		
		if(sus) return (ret == INT_MAX) ? -1 : ret;
		if(M * k - 1 < l) L = M;
		if(r < M * (k - 1) + 1) R = M;
	}
	return -1;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> k >> n >> m >> q;
	for(int i = 0; i < m; i++) {
		int s, f, t;
		cin >> s >> f >> t;
		mp[MP(s + 1, f + 1)] = t;
	}
	
	build(1, n / k + 1);
	
	while(q--) {
		int l, r;
		cin >> l >> r;
		l++, r++;
		
		if(inmap(MP(l, r)))
			cout << mp[MP(l, r)] << '\n';
		else
			cout << query(l, r) << '\n';
	}
	return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44