Submission #707100

#	Time	Username	Problem	Language	Result	Execution time	Memory
707100		600Mihnea	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	47 ms	9832 KiB

skyscraper

#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

const int INF = (int)1e9 + 7;

struct T
{
	int pos;
	int delta;
};

bool operator < (T a, T b)
{
	return make_pair(a.pos, a.delta) < make_pair(b.pos, b.delta);
}

signed main()
{
#ifdef ONPC	
	FILE* stream;
	freopen_s(&stream, "input.txt", "r", stdin);
#else
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif

	int dim, cntofs;
	cin >> dim >> cntofs;

	vector<T> ofs(cntofs);
	vector<vector<int>> cine(dim);
	for (int i = 0; i < cntofs; i++)
	{
		cin >> ofs[i].pos >> ofs[i].delta;
		assert(0 <= ofs[i].pos && ofs[i].pos < dim);
	}
	int Init = ofs[0].pos;
	int Query = ofs[1].pos;

	sort(ofs.begin(), ofs.end());

	vector<vector<int>> deltas(dim);

	{
		assert(!ofs.empty());
		vector<T> newofs = { ofs[0] };
		for (int i = 1; i < cntofs; i++)
		{
			if (make_pair(ofs[i].pos, ofs[i].delta) != make_pair(ofs[i - 1].pos, ofs[i - 1].delta))
			{
				newofs.push_back(ofs[i]);
			}
		}
		ofs = newofs;
		cntofs = (int)ofs.size();
		for (auto& of : ofs)
		{
			deltas[of.pos].push_back(of.delta);
		}
		for (auto& delta : deltas)
		{
			sort(delta.begin(), delta.end());
		}
	}

	auto has = [&](int pos, int delta)
	{
		int low = 0, high = (int)deltas[pos].size() - 1;
		while (low <= high)
		{
			int mid = (low + high) / 2;
			if (deltas[pos][mid] == delta)
			{
				return 1;
			}
			if (deltas[pos][mid] < delta)
			{
				low = mid + 1;
			}
			else
			{
				high = mid - 1;
			}
		}
		return 0;
	};

	assert((int)ofs.size() == cntofs);

	for (int i = 0; i < cntofs; i++)
	{
		assert(0 <= ofs[i].pos && ofs[i].pos < dim);
		cine[ofs[i].pos].push_back(i);
	}

	
	vector<int> dp(dim, INF);

	priority_queue<pair<int, int>> pq;

	auto relax = [&](int i, int val)
	{
		if (val < dp[i])
		{
			dp[i] = val;
			pq.push({ -dp[i], i });
		}
	};

	set<pair<int, int>> s_delta_rest;
	// {delta, rest}
	for (auto& it : ofs)
	{
		s_delta_rest.insert({ it.delta, it.pos % it.delta });
	}
	vector<pair<int, int>> v_delta_rest;

	for (auto& it : s_delta_rest)
	{
		v_delta_rest.push_back(it);
	}

	int states = (int)v_delta_rest.size();
	vector<vector<int>> cool(states);
	for (int it = 0; it < states; it++)
	{
		int i = v_delta_rest[it].first, j = v_delta_rest[it].second;
		for (int p = j; p < dim; p += i)
		{
			if (!cine[p].empty())
			{
				cool[it].push_back(p);
			}
		}
	}

	auto fnd = [&](pair<int, int> it)
	{
		assert(0 <= it.second && it.second < it.first);
		int l = 0, r = (int)v_delta_rest.size() - 1;
		while (l <= r)
		{
			int m = (l + r) / 2;
			if (v_delta_rest[m] == it)
			{
				return m;
			}
			if (v_delta_rest[m] < it)
			{
				l = m + 1;
			}
			else
			{
				r = m - 1;
			}
		}
		assert(0);
	};

	relax(Init, 0);
	
	while (!pq.empty())
	{
		auto it = pq.top();
		pq.pop();
		int loc = it.second;
		if (-it.first != dp[loc])
		{
			continue;
		}
		for (auto& i : cine[loc])
		{
			int what = fnd({ ofs[i].delta, loc % ofs[i].delta });
			int pz = lower_bound(cool[what].begin(), cool[what].end(), loc) - cool[what].begin();
			assert(0 <= pz && pz < (int)cool[what].size());
			assert(cool[what][pz] == loc);
			for (int j = pz - 1; j >= 0; j--)
			{
				int loc2 = cool[what][j];
				int posdif = abs(ofs[i].pos - loc2);
				relax(loc2, dp[loc] + posdif / ofs[i].delta);
				if (has(cool[what][j], ofs[i].delta)) break;
			}
			for (int j = pz + 1; j < (int)cool[what].size(); j++)
			{
				int loc2 = cool[what][j];
				int posdif = abs(ofs[i].pos - loc2);
				relax(loc2, dp[loc] + posdif / ofs[i].delta);
				if (has(cool[what][j], ofs[i].delta)) break;
			}
		}
	}
	int sol = (dp[Query] == INF) ? (-1) : (dp[Query]);
	cout << sol << "\n";
	return 0;
}

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