Submission #826076

#	Time	Username	Problem	Language	Result	Execution time	Memory
826076		tolbi	Sky Walking (IOI19_walk)	C++17	24 / 100	2700 ms	1048576 KiB

walk

#pragma optimize("Bismilahirrahmanirrahim")
//█▀█─█──█──█▀█─█▀█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define vint(x) vector<int> x
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define tol(bi) (1LL<<((int)(bi)))
typedef long long ll;
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "walk.h"

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	ll n = x.size();
	ll m = y.size();
	vector<ll> lelx(n);
	iota(lelx.begin(), lelx.end(), 0);
	vector<ll> lely(m,-1);
	vector<array<ll,4>> isl;
	for (ll i = 0; i < m; i++){
		isl.push_back({l[i],y[i],i,1});
		isl.push_back({r[i]+1,y[i],i,-1});
	}
	sortarr(isl);
	ll indi = 0;
	set<pair<ll,ll>> st;
	vector<vector<pair<ll,ll>>> arr(n);
	vector<ll> xpos(n);
	for (ll i = 0; i < n; ++i)
	{
		xpos[i]=x[i];
	}
	vector<ll> ypos(n,0);
	for (ll i = 0; i < n; i++){
		while (indi<isl.size() && isl[indi][0]<=i){
			if (isl[indi][3]==1){
				st.insert({isl[indi][1],isl[indi][2]});
			}
			else {
				st.erase({isl[indi][1],isl[indi][2]});
			}
			indi++;
		}
		auto it = st.begin();
		while (it!=st.end()){
			if (it->first>h[i]) break;
			ll node = arr.size();
			xpos.push_back(x[i]);
			ypos.push_back(it->first);
			arr.push_back(vector<pair<ll,ll>>());
			if (lely[it->second]!=-1){
				arr[lely[it->second]].push_back({node,abs(xpos[node]-xpos[lely[it->second]])});
				arr[node].push_back({lely[it->second],abs(xpos[node]-xpos[lely[it->second]])});
			}
			arr[lelx[i]].push_back({node,abs(ypos[node]-ypos[lelx[i]])});
			arr[node].push_back({lelx[i],abs(ypos[node]-ypos[lelx[i]])});
			lelx[i]=node;
			lely[it->second]=node;
			it++;
		}
	}
	vector<ll> dp(arr.size(), -1);
	priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
	pq.push({0,s});
	while (pq.size()){
		ll node = pq.top().second;
		ll w = pq.top().first;
		pq.pop();
		if (dp[node]!=-1) continue;
		dp[node]=w;
		for (ll i = 0; i < arr[node].size(); i++){
			if (dp[arr[node][i].first]!=-1) continue;
			pq.push({w+arr[node][i].second,arr[node][i].first});
		}
	}
	return dp[g];
}

Compilation message (stderr)

walk.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismilahirrahmanirrahim")
      | 
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:46:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   while (indi<isl.size() && isl[indi][0]<=i){
      |          ~~~~^~~~~~~~~~~
walk.cpp:82:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for (ll i = 0; i < arr[node].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43