QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#520938#8649. Escape Route 2green_gold_dog#Compile Error//C++204.1kb2024-08-15 17:44:002024-08-15 17:44:00

Judging History

你现在查看的是最新测评结果

  • [2024-08-15 17:44:00]
  • 评测
  • [2024-08-15 17:44:00]
  • 提交

answer

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;

constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007, LOG = 17;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;

random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());

template<typename T>
bool assign_max(T& a, T b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}

template<typename T>
bool assign_min(T& a, T b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}

template<typename T>
T square(T a) {
	return a * a;
}

template<>
struct std::hash<pair<ll, ll>> {
	ll operator() (pair<ll, ll> p) const {
		return ((__int128)p.first * MOD + p.second) % INF64;
	}
};

struct LA {
	vector<vector<ll>> arr;
	vector<vector<vector<ll>>> smk;
	vector<vector<vector<pair<ll, ll>>>> binup;
	map<pair<ll, ll>, ll> mind;
	LA(vector<vector<pair<ll, ll>>> a, ll dt) {
		ll n = a.size();
		arr.resize(n);
		vector<vector<ll>> ends(n);
		for (ll i = 0; i < n; i++) {
			sort(a[i].begin(), a[i].end());
			ll bto = INF32;
			while (!a[i].empty()) {
				if (a[i].back().second < bto) {
					bto = a[i].back().second;
					arr[i].push_back(a[i].back().first);
					ends[i].push_back(a[i].back().second);
				}
				a[i].pop_back();
			}
			reverse(arr[i].begin(), arr[i].end());
			reverse(ends[i].begin(), ends[i].end());
		}
		binup.resize(n);
		for (ll i = n - 1; i >= 0; i--) {
			binup[i].resize(arr[i].size());
			for (ll j = 0; j < arr[i].size(); j++) {
				binup[i][j].resize(LOG);
				binup[i][j][0] = make_pair(0, ends[i][j]);
				for (ll k = 1; k < LOG; k++) {
					pair<ll, ll> ans = binup[i][j][k - 1];
					ll nextv = i + (1 << (k - 1));
					if (nextv >= n) {
						break;
					}
					ll num = lower_bound(arr[nextv].begin(), arr[nextv].end(), ans.second) - arr[nextv].begin();
					if (num == arr[nextv].size()) {
						num = 0;
						ans.first++;
						ans.second = 0;
					}
					binup[i][j][k] = make_pair(ans.first + binup[nextv][num][k - 1].first, binup[nextv][num][k - 1].second);
				}
			}
		}
		smk.resize(n);
		for (ll i = 0; i < n; i++) {
			vector<ll> all = arr[i];
			for (ll sz = 0; sz < LOG; sz++) {
				if (i + (1 << sz) > n) {
					break;
				}
				smk[i].push_back(vector<ll>(0, 0));
				ll lst = INF64;
				while (!all.empty()) {
					ll x = get(i, 1 << sz, all.back(), dt);
					if (x != lst) {
						smk[i].back().push_back(all.back());
						lst = x;
					}
					all.pop_back();
				}
				reverse(smk[i].back().begin(), smk[i].back().end());
				assert(smk[i].size() <= n / (1 << size));
				all = smk[i].back();
			}
		}
	}
	ll get(ll v, ll x, ll st, ll dt) {
		ll d = 0, t = st;
		for (ll i = LOG - 1; i >= 0; i--) {
			if ((x >> i) & 1) {
				x ^= 1 << i;
				ll num = lower_bound(arr[v].begin(), arr[v].end(), t) - arr[v].begin();
				if (num == arr[v].size()) {
					num = 0;
					d++;
					t = 0;
				}
				d += binup[v][num][i].first;
				t = binup[v][num][i].second;
				v += 1 << i;
			}
		}
		return dt * d + t;
	}
	ll get(ll v, ll x, ll dt) {
		if (mind.find(make_pair(v, x)) != mind.end()) {
			return mind[make_pair(v, x)];
		}
		ll p2 = 0;
		ll nx = x;
		while (nx > 1) {
			nx /= 2;
			p2++;
		}
		ll ans = INF64;
		for (auto i : smk[v][p2]) {
			assign_min(ans, get(v, x, i, dt) - i);
		}
		return mind[make_pair(v, x)] = ans;
	}
};

void solve() {
	ll n, t;
	cin >> n >> t;
	vector<vector<pair<ll, ll>>> to(n - 1);
	for (ll i = 0; i < n - 1; i++) {
		ll col;
		cin >> col;
		for (ll j = 0; j < col; j++) {
			ll a, b;
			cin >> a >> b;
			to[i].emplace_back(a, b);
		}
	}
	LA la(to, t);
	ll q;
	cin >> q;
	for (ll i = 0; i < q; i++) {
		ll l, r;
		cin >> l >> r;
		l--;
		cout << la.get(l, r - l - 1, t) << '\n';
	}
}

int main() {
	if (IS_FILE) {
		freopen("", "r", stdin);
		freopen("", "w", stdout);
	}
    	ios_base::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
	ll t = 1;
	if (IS_TEST_CASES) {
		cin >> t;
	}
	for (ll i = 0; i < t; i++) {
		solve();
	}
}

Details

In file included from /usr/include/c++/13/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:106,
                 from answer.code:3:
answer.code: In constructor ‘LA::LA(std::vector<std::vector<std::pair<long long int, long long int> > >, ll)’:
answer.code:113:64: error: invalid operands of types ‘int’ and ‘<unresolved overloaded function type>’ to binary ‘operator<<’
  113 |                                 assert(smk[i].size() <= n / (1 << size));
      |                                                              ~~^~~~~~~
answer.code: In function ‘int main()’:
answer.code:180:24: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  180 |                 freopen("", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~
answer.code:181:24: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  181 |                 freopen("", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~