Submission #208039

#	Time	Username	Problem	Language	Result	Execution time	Memory
208039		Lawliet	Sky Walking (IOI19_walk)	C++17	33 / 100	770 ms	288940 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;

const int MAXN = 2000010;
const lli INF = 1000000000000000000LL;

class SegmentTree
{
	public:

		int getLeft(int node) { return 2*node; }
		int getRight(int node) { return 2*node + 1; }

		void update(int node, int l, int r, int i, lli v)
		{
			if( i < l || r < i ) return;

			if( l == r )
			{
				mn[node] = v;
				return;
			}

			int m = ( l + r )/2;

			update( getLeft(node) , l , m , i , v );
			update( getRight(node) , m + 1 , r , i , v );

			mn[node] = min( mn[ getLeft(node) ] , mn[ getRight(node) ] );
		}

		lli query(int node, int l, int r, int i, int j)
		{
			if( j < l || r < i ) return INF;
			if( i <= l && r <= j ) return mn[node];

			int m = ( l + r )/2;

			lli mnLeft = query( getLeft(node) , l , m , i , j );
			lli mnRight = query( getRight(node) , m + 1 , r , i , j );

			return min( mnLeft , mnRight );
		}

		SegmentTree()
		{
			for(int i = 0 ; i < 4*MAXN ; i++)
				mn[i] = INF;
		}

	private:

		lli mn[4*MAXN];
};

int n, m;
int cntNode;

bool wasUpdated[MAXN];

vector< int > sweep[MAXN];
vector< int > building[MAXN];
vector< int > intersection[MAXN];

map< int , int > realY;

SegmentTree up;
SegmentTree down;

void compress(vector<int>& v)
{
	set< int > s;
	map< int , int > conv;

	for(int i = 0 ; i < (int) v.size() ; i++)
		s.insert( v[i] );

	int cnt = 0;

	for(auto it = s.begin() ; it != s.end() ; it++)
	{
		conv[ *it ] = ++cnt;
		realY[ cnt ] = *it;
	}

	for(int i = 0 ; i < (int) v.size() ; i++)
		v[i] = conv[ v[i] ];
}

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int a, int b) 
{
	n = x.size(); m = l.size();

	compress( y );

	for(int i = 0 ; i < m ; i++)
	{
		sweep[ l[i] ].push_back( -i - 1 );
		sweep[ r[i] ].push_back( i + 1 );

		building[ l[i] ].push_back( y[i] );
		building[ r[i] ].push_back( y[i] );
	}

	for(int i = 0 ; i < (int) building[b].size() ; i++)
	{
		int curHeight = building[b][i];

		up.update( 1 , 1 , m , curHeight , 2*realY[ curHeight ] );
		down.update( 1 , 1 , m , curHeight , 0 );
	}

	lli ans = INF;

	for(int i = n - 2 ; i >= 0 ; i--)
	{
		sort( sweep[i].begin() , sweep[i].end() );

		vector< int > all;
		vector< pair<lli,int> > updates;

		while( !sweep[i].empty() && sweep[i].back() > 0 )
		{
			int cur = sweep[i].back(); cur = cur - 1;
			sweep[i].pop_back();

			all.push_back( y[cur] );
			wasUpdated[ y[cur] ] = true;

			lli ansUp = up.query( 1 , 1 , m , y[cur] , m );
			lli ansDown = down.query( 1 , 1 , m , 1 , y[cur] );

			ansUp -= realY[ y[cur] ];
			ansDown += realY[ y[cur] ];

			lli curAns = min( ansUp , ansDown );

			updates.push_back( { curAns , y[cur] } );
		}

		while( !updates.empty() )
		{
			lli curVal = updates.back().first;
			int curHeight = updates.back().second;
			updates.pop_back();

			up.update( 1 , 1 , m , curHeight , curVal + realY[ curHeight ] );
			down.update( 1 , 1 , m , curHeight , curVal - realY[ curHeight ] );
		}

		if( i == 0 )
			ans = up.query( 1 , 1 , m , 1 , m );

		while( !sweep[i].empty() )
		{
			int cur = sweep[i].back(); cur = -cur - 1;
			sweep[i].pop_back();

			if( wasUpdated[ y[cur] ] ) continue;

			up.update( 1 , 1 , m , y[cur] , INF );
			down.update( 1 , 1 , m , y[cur] , INF );
		}

		while( !all.empty() )
		{
			wasUpdated[ all.back() ] = false;
			all.pop_back();
		}
	}

	ans += x[n - 1] - x[0];

	if( ans >= INF ) return -1;
	return ans;
}

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