Submission #671142

#	Time	Username	Problem	Language	Result	Execution time	Memory
671142		NothingXD	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	57 / 100	1079 ms	4820 KiB

skyscraper

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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
/*typedef __uint128_t L;
struct FastMod {
	ull b, m;
	FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
	ull reduce(ull a) {
		ull q = (ull)((L(m) * a) >> 64);
		ull r = a - q * b; // can be proven that 0 <= r < 2*b
		return r >= b ? r - b : r;
	}
};
FastMod FM(2);*/
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e4 + 10;

int n, m, a[maxn], b[maxn], h[maxn];
map<pii,bool> mp;
vector<int> val[maxn], idx[maxn];
vector<pii> num;

void dijkstra(int st){
	memset(h, 63, sizeof h);
	h[st] = 0;
	priority_queue<pii, vector<pii>, greater<pii>> q;
	q.push({0, st});
	while(!q.empty()){
		int v = q.top().S, w = q.top().F;
		q.pop();
		if (w > h[v]) continue;
		for (auto x: val[v]){
			int tmp = v % x;
			int ptr = lower_bound(all(num), MP(x, tmp)) - num.begin();
			int PTR = lower_bound(all(idx[ptr]), v) - idx[ptr].begin();
			int l = tmp, r = n-1;
			if (PTR != 0) l = idx[ptr][PTR-1];
			if (PTR + 1 != idx[ptr].size()) r = idx[ptr][PTR+1];
			for (int u = l; u <= r; u += x){
				int dis = abs(v - u) / x;
				if (h[u] > h[v] + dis){
					h[u] = h[v] + dis;
					q.push({h[u], u});
				}
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= m; i++){
		cin >> a[i] >> b[i];
		val[a[i]].push_back(b[i]);
		num.push_back({b[i], a[i] % b[i]});
	}

	sort(all(num));
	num.resize(distance(num.begin(), unique(all(num))));

	for (int i = 1; i <= m; i++){
		int ptr = lower_bound(all(num), MP(b[i], a[i] % b[i])) - num.begin();
		idx[ptr].push_back(a[i]);
	}

	for (int i = 0; i < num.size(); i++){
		sort(all(idx[i]));
		idx[i].resize(distance(idx[i].begin(), unique(all(idx[i]))));
	}

	dijkstra(a[1]);
	cout << (h[a[2]] > n*n? -1: h[a[2]]) << '\n';

	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void dijkstra(int)':
skyscraper.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    if (PTR + 1 != idx[ptr].size()) r = idx[ptr][PTR+1];
      |        ~~~~~~~~^~~~~~~~~~~~~~~~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for (int i = 0; i < num.size(); i++){
      |                  ~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43