Submission #8363205


Source Code Expand

Copy

#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <cmath>

using namespace std;
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int32_t N, M;
int64_t D[109000];
std::pair<int, std::pair<int64_t, int>> range[109000];
const int64_t INF = 1090001000000000;
int main()
{
	using std::endl;

	cin >> N >> M;
	for (size_t i = 0; i < M; i++)
	{
		int a, b, c;
		cin >> a >> b >> c; --a; 
		range[i].first = a;
		range[i].second.first = c;
		range[i].second.second = b;
	}
	std::sort(range, range + M);
	std::priority_queue<std::pair<int64_t, int>, std::vector<std::pair<int64_t, int>>, std::greater<>> que;

	for (size_t i = 0; i < N; i++)
	{
		D[i] = INF;
	}
	D[0] = 0;
	que.push({ 0, 0 });
	auto iter = range;
	auto iterend = range;
	while (!que.empty())
	{
		auto pos = que.top(); que.pop();

		while (iterend != range+M && iterend->first <= pos.second)
		{
			++iterend;
		}
		while (iter != iterend && iter->second.second <= pos.second)
		{
			++iter;
		}

		while (iter != iterend)
		{
			auto newcost = pos.first + iter->second.first;
			if (D[iter->second.second - 1] > newcost) {
				D[iter->second.second - 1] = newcost;
				que.push({ pos.first + iter->second.first, iter->second.second - 1 });
			}

			++iter;
		}


	}

	if (D[N - 1] == INF) {
		D[N - 1] = -1;
	}
	cout << D[N - 1] << endl;

	return 0;
}
#endif

#if 0
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <cmath>

using namespace std;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int32_t N;
int32_t A[100000];
int32_t B[100000];
int32_t Asort[100000];
int32_t Bsort[100000];
bool isok[3][300000][20];

int main()
{
	using std::endl;

	cin >> N;
	for (size_t i = 0; i < N; i++)
	{
		cin >> A[i];
	}
	for (size_t i = 0; i < N; i++)
	{
		cin >> B[i];
	}

	for (size_t i = 0; i < N; i++)
	{
		Asort[i] = A[i];
		Bsort[i] = B[i];
	}

	std::sort(Asort, Asort + N);
	std::sort(Bsort, Bsort + N);
	Bsort[N] = 1100000000;

	if(N==2){
		bool ok2 = true;
		for (size_t i = 0; i < N; i++)
		{
			ok2 &= B[i] >= A[i];
		}
		if (ok2)
		{
			cout << "Yes" << endl;
		}
		else {
			cout << "No" << endl;
		};
		return 0;
	}

	isok[0][0][0] = true;
	for (size_t i = 0; i < N; i++)
	{
		if (i > 0) { isok[0][i][0] = Bsort[i - 1] >= Asort[i]; }
		isok[1][i][0] = Bsort[i] >= Asort[i];
		isok[2][i][0] = Bsort[i+1] >= Asort[i];
	}
	for (size_t i = N; i < 3*N; i++)
	{
		isok[0][i][0] = true;
		isok[1][i][0] = true;
		isok[2][i][0] = true;
	}

	for (size_t b = 1; b < 20; b++)
	{
		for (size_t i = 0; i < 2 * N; i++)
		{
			auto next = i + (1 << (b - 1));
			if (next >= 2*N) {
				next = i;
			}
			isok[0][i][b] = isok[0][i][b-1] & isok[0][next][b-1];
			isok[1][i][b] = isok[1][i][b-1] & isok[1][next][b-1];
			isok[2][i][b] = isok[2][i][b-1] & isok[2][next][b-1];
		}
	}

	for (size_t cou = 0; cou < N; cou++)
	{
		if (B[cou] < A[cou]) { continue; }
		auto aindex = std::upper_bound(Asort, Asort + N, A[cou]) - Asort - 1;
		auto bindex = std::lower_bound(Bsort, Bsort + N, B[cou]) - Bsort;

		bool ok = true;
		if (aindex < bindex)
		{
			int i = 0;
			for (int b = 20 - 1; b >= 0; b--)
			{
				auto next = i + (1 << (b ));
				if (aindex < next) { continue; }

				ok &= isok[1][i][b];
				i = next;
			}
			assert(i == aindex);
			++i;
			for (int b = 20 - 1; b >= 0; b--)
			{
				auto next = i + (1 << (b ));
				if (bindex < next) { continue; }

				ok &= isok[0][i][b];
				i = next;
			}
			assert(i == bindex);
			++i;
			for (int b = 20 - 1; b >= 0; b--)
			{
				auto next = i + (1 << (b ));
				if (N < next) { continue; }

				ok &= isok[1][i][b];
				i = next;
			}
			assert(i == N);
		}
		else
		{
			int i = 0;
			for (int b = 20 - 1; b >= 0; b--)
			{
				auto next = i + (1 << (b ));
				if (bindex < next) { continue; }

				ok &= isok[1][i][b];
				i = next;
			}
			assert(i == bindex);
			if (aindex != bindex)
			{
				for (int b = 20 - 1; b >= 0; b--)
				{
					auto next = i + (1 << (b));
					if (aindex < next + 1) { continue; }

					ok &= isok[2][i][b];
					i = next;
				}
				assert(i+1 == aindex);
				++i;
			}
			++i;
			for (int b = 20 - 1; b >= 0; b--)
			{
				auto next = i + (1 << (b ));
				if (N < next) { continue; }

				ok &= isok[1][i][b];
				i = next;
			}
			assert(i == N);

			bool ok2 = true;
			for (size_t i = 0; i < N; i++)
			{
				ok2 &= Bsort[i] >= Asort[i];
			}
			ok = ok2;

		}

		if (ok)
		{
			cout << "Yes" << endl;
			return 0;
		}

	}



	cout << "No" << endl;
	return 0;
}
#endif

Submission Info

Submission Time
Task D - Shortest Path on a Line
User eiya
Language C++14 (Clang 3.8.0)
Score 600
Code Size 5537 Byte
Status
Exec Time 276 ms
Memory 5364 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample01.txt, sample02.txt, sample03.txt
All 600 / 600 sample01.txt, sample02.txt, sample03.txt, in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, sample01.txt, sample02.txt, sample03.txt
Case Name Status Exec Time Memory
in01.txt 3 ms 256 KB
in02.txt 3 ms 256 KB
in03.txt 3 ms 256 KB
in04.txt 3 ms 256 KB
in05.txt 3 ms 256 KB
in06.txt 3 ms 256 KB
in07.txt 273 ms 4088 KB
in08.txt 249 ms 2816 KB
in09.txt 266 ms 5364 KB
in10.txt 261 ms 5236 KB
in11.txt 251 ms 3832 KB
in12.txt 264 ms 5108 KB
in13.txt 274 ms 4088 KB
in14.txt 275 ms 4216 KB
in15.txt 258 ms 4344 KB
in16.txt 268 ms 4344 KB
in17.txt 274 ms 5364 KB
in18.txt 270 ms 4472 KB
in19.txt 202 ms 2816 KB
in20.txt 209 ms 2944 KB
in21.txt 222 ms 3072 KB
in22.txt 213 ms 2944 KB
in23.txt 269 ms 2944 KB
in24.txt 275 ms 3072 KB
in25.txt 276 ms 2944 KB
in26.txt 237 ms 3452 KB
in27.txt 211 ms 3328 KB
in28.txt 234 ms 3708 KB
in29.txt 251 ms 3580 KB
in30.txt 230 ms 3580 KB
in31.txt 255 ms 3328 KB
in32.txt 246 ms 3200 KB
in33.txt 236 ms 3452 KB
in34.txt 1 ms 256 KB
sample01.txt 1 ms 256 KB
sample02.txt 1 ms 256 KB
sample03.txt 1 ms 256 KB