Submission #826062

#	Time	Username	Problem	Language	Result	Execution time	Memory
826062		tolbi	Sky Walking (IOI19_walk)	C++17	0 / 100	2360 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) {
	int n = x.size();
	int m = y.size();
	vector<int> lelx(n);
	iota(lelx.begin(), lelx.end(), 0);
	vector<int> lely(m,-1);
	vector<array<int,4>> isl;
	for (int 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);
	int indi = 0;
	set<pair<int,int>> st;
	vector<vector<pair<int,int>>> arr(n);
	vector<int> xpos(n);
	for (int i = 0; i < n; ++i)
	{
		xpos[i]=x[i];
	}
	vector<int> ypos(n,0);
	for (int 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;
			int node = arr.size();
			xpos.push_back(x[i]);
			ypos.push_back(it->first);
			arr.push_back(vector<pair<int,int>>());
			if (lely[it->second]!=-1){
				arr[lely[it->second]].push_back({node,xpos[node]-xpos[lely[it->second]]});
				arr[node].push_back({lely[it->second],xpos[node]-xpos[lely[it->second]]});
			}
			arr[lelx[i]].push_back({node,ypos[node]-ypos[lelx[i]]});
			arr[node].push_back({lelx[i],ypos[node]-ypos[lelx[i]]});
			lelx[i]=node;
			lely[it->second]=node;
			it++;
		}
	}
	vector<int> dp(arr.size(), -1);
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	pq.push({0,s});
	while (pq.size()){
		int node = pq.top().second;
		int w = pq.top().first;
		pq.pop();
		if (dp[node]!=-1) continue;
		dp[node]=w;
		for (int 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: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   while (indi<isl.size() && isl[indi][0]<=i){
      |          ~~~~^~~~~~~~~~~
walk.cpp:82:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for (int i = 0; i < arr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~

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