Submission #322145

#	Time	Username	Problem	Language	Result	Execution time	Memory
322145		arnold518	Sky Walking (IOI19_walk)	C++14	0 / 100	4085 ms	171344 KiB

walk

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const ll INF = 1e15;

struct Build
{
	int X, H;
};

struct Line
{
	int L, R, Y;
};

int N, M, S, E;
Build A[MAXN+10];
Line B[MAXN+10];
vector<int> V[MAXN+10];
vector<ll> dist[MAXN+10];
vector<pii> L[MAXN+10], R[MAXN+10];

struct Queue
{
	int x, y; ll w;
	bool operator < (const Queue &p) const
	{
		return w>p.w;
	}
};

struct SEG
{
	vector<pii> tree[MAXN*4+10];
	void init(int node, int tl, int tr)
	{
		if(tl==tr)
		{
			tree[node].push_back(pii(A[tl].H, tl));
			return;
		}
		int mid=tl+tr>>1;
		init(node*2, tl, mid);
		init(node*2+1, mid+1, tr);
		tree[node].resize(tr-tl+1);
		merge(tree[node*2].begin(), tree[node*2].end(), tree[node*2+1].begin(), tree[node*2+1].end(), tree[node].begin(), greater<pii>());
	}
	void get(int node, int tl, int tr, int l, int r, int x, vector<int> &V)
	{
		if(l<=tl && tr<=r)
		{
			for(auto it : tree[node])
			{
				if(it.first<x) break;
				V.push_back(it.second);
			}
			return;
		}
		if(r<tl || tr<l) return;
		int mid=tl+tr>>1;
		get(node*2, tl, mid, l, r, x, V);
		get(node*2+1, mid+1, tr, l, r, x, V);
	}
}seg;

ll min_distance(vector<int> _X, vector<int> _H, vector<int> _L, vector<int> _R, vector<int> _Y, int _S, int _E)
{
	N=_X.size(); M=_L.size();
	for(int i=0; i<N; i++) A[i+1]={_X[i], _H[i]};
	for(int i=0; i<M; i++) B[i+1]={_L[i]+1, _R[i]+1, _Y[i]};
	S=_S+1; E=_E+1;
	seg.init(1, 1, N);

	for(int i=1; i<=N; i++) V[i].push_back(0);
	for(int i=1; i<=M; i++)
	{
		vector<int> T;
		seg.get(1, 1, N, B[i].L, B[i].R, B[i].Y, T);
		sort(T.begin(), T.end());
		for(auto j : T)
		{
			V[j].push_back(B[i].Y);
		}
	}

	for(int i=1; i<=N; i++)
	{
		sort(V[i].begin(), V[i].end());
		dist[i]=vector<ll>(V[i].size(), INF);
		L[i]=vector<pii>(V[i].size(), pii(0, 0));
		R[i]=vector<pii>(V[i].size(), pii(N+1, 0));
	}

	for(int i=1; i<=M; i++)
	{
		vector<int> T;
		seg.get(1, 1, N, B[i].L, B[i].R, B[i].Y, T);
		sort(T.begin(), T.end());
		int by=lower_bound(V[B[i].L].begin(), V[B[i].L].end(), B[i].Y)-V[B[i].L].begin(), bx=B[i].L;
		for(auto j : T)
		{
			int y=lower_bound(V[j].begin(), V[j].end(), B[i].Y)-V[j].begin(), x=j;
			L[x][y]=pii(bx, by);
			R[bx][by]=pii(x, y);
			by=y; bx=x;
		}
	}

	priority_queue<Queue> PQ;
	PQ.push({S, 0, 0});
	while(!PQ.empty())
	{
		Queue now=PQ.top(); PQ.pop();
		if(dist[now.x][now.y]<=now.w) continue;
		dist[now.x][now.y]=now.w;

		if(now.y+1<V[now.x].size()) PQ.push({now.x, now.y+1, now.w+V[now.x][now.y+1]-V[now.x][now.y]});
		if(now.y-1>=0) PQ.push({now.x, now.y-1, now.w+V[now.x][now.y]-V[now.x][now.y-1]});
		if(L[now.x][now.y].first>=1) PQ.push({L[now.x][now.y].first, L[now.x][now.y].second, now.w+A[now.x].X-A[L[now.x][now.y].first].X});
		if(R[now.x][now.y].first<=N) PQ.push({R[now.x][now.y].first, R[now.x][now.y].second, now.w-A[now.x].X+A[R[now.x][now.y].first].X});
	}
	if(dist[E][0]==INF) return -1;
	return dist[E][0];
}

Compilation message (stderr)

walk.cpp: In member function 'void SEG::init(int, int, int)':
walk.cpp:48:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int mid=tl+tr>>1;
      |           ~~^~~
walk.cpp: In member function 'void SEG::get(int, int, int, int, int, int, std::vector<int>&)':
walk.cpp:66:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |   int mid=tl+tr>>1;
      |           ~~^~~
walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:123:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   if(now.y+1<V[now.x].size()) PQ.push({now.x, now.y+1, now.w+V[now.x][now.y+1]-V[now.x][now.y]});
      |      ~~~~~~~^~~~~~~~~~~~~~~~

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