Submission #322331

#	Time	Username	Problem	Language	Result	Execution time	Memory
322331		arnold518	Sky Walking (IOI19_walk)	C++14	33 / 100	230 ms	27084 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];

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

struct SEG
{
	int tree[MAXN*4+10];
	void update(int node, int tl, int tr, int l, int r, int k)
	{
		if(tree[node]!=0 && tl!=tr)
		{
			tree[node*2]=tree[node];
			tree[node*2+1]=tree[node];
			tree[node]=0;
		}
		if(l<=tl && tr<=r) { tree[node]=k; return; }
		if(r<tl || tr<l) return;
		int mid=tl+tr>>1;
		update(node*2, tl, mid, l, r, k);
		update(node*2+1, mid+1, tr, l, r, k);
	}
	int query(int node, int tl, int tr, int p)
	{
		if(tree[node]!=0 && tl!=tr)
		{
			tree[node*2]=tree[node];
			tree[node*2+1]=tree[node];
			tree[node]=0;
		}
		if(tl==tr) return tree[node];
		int mid=tl+tr>>1;
		if(p<=mid) return query(node*2, tl, mid, p);
		else return query(node*2+1, mid+1, tr, p);
	}
}seg;

vector<pll> adj[MAXN+10];
ll dist[MAXN+10];

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;
	
	B[M+1]={S, S, 0};
	B[M+2]={E, E, 0};
	sort(B+1, B+M+3, [&](const Line &p, const Line &q)
	{
		return p.Y<q.Y;
	});

	for(int i=1; i<=M+2; i++)
	{
		int u=seg.query(1, 1, N, B[i].L);
		if(u)
		{
			adj[u].push_back({i, B[i].Y-B[u].Y});
			adj[i].push_back({u, B[i].Y-B[u].Y});
		}
		u=seg.query(1, 1, N, B[i].R);
		if(u)
		{
			adj[u].push_back({i, B[i].Y-B[u].Y});
			adj[i].push_back({u, B[i].Y-B[u].Y});
		}
		seg.update(1, 1, N, B[i].L, B[i].R, i);
	}

	for(int i=1; i<=M+2; i++) dist[i]=INF;
	priority_queue<Queue> PQ;
	PQ.push({1, 0});
	while(!PQ.empty())
	{
		Queue now=PQ.top(); PQ.pop();
		if(dist[now.u]<=now.w) continue;
		dist[now.u]=now.w;

		for(auto nxt : adj[now.u])
		{
			PQ.push({nxt.first, nxt.second+now.w});
		}
	}
	if(dist[2]==INF) return -1;
	return dist[2]+A[N].X-A[1].X;
}

Compilation message (stderr)

walk.cpp: In member function 'void SEG::update(int, int, int, int, int, int)':
walk.cpp:48:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int mid=tl+tr>>1;
      |           ~~^~~
walk.cpp: In member function 'int SEG::query(int, int, int, int)':
walk.cpp:61:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |   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:112:17: warning: narrowing conversion of 'nxt.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
  112 |    PQ.push({nxt.first, nxt.second+now.w});
      |             ~~~~^~~~~

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