oj.uz

Submission #208039

# Submission time Handle Problem Language Result Execution time Memory
208039 2020-03-09T21:00:21 Z Lawliet Sky Walking (IOI19_walk) C++17
33 / 100
 770 ms 288940 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 151 ms 266488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 266488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 269432 KB Output is correct
2 Correct 622 ms 283132 KB Output is correct
3 Correct 669 ms 285384 KB Output is correct
4 Correct 739 ms 288892 KB Output is correct
5 Correct 720 ms 288940 KB Output is correct
6 Correct 724 ms 288888 KB Output is correct
7 Correct 419 ms 279928 KB Output is correct
8 Correct 732 ms 288760 KB Output is correct
9 Correct 673 ms 288824 KB Output is correct
10 Correct 439 ms 282228 KB Output is correct
11 Correct 166 ms 268052 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 269432 KB Output is correct
2 Correct 622 ms 283132 KB Output is correct
3 Correct 669 ms 285384 KB Output is correct
4 Correct 739 ms 288892 KB Output is correct
5 Correct 720 ms 288940 KB Output is correct
6 Correct 724 ms 288888 KB Output is correct
7 Correct 419 ms 279928 KB Output is correct
8 Correct 732 ms 288760 KB Output is correct
9 Correct 673 ms 288824 KB Output is correct
10 Correct 439 ms 282228 KB Output is correct
11 Correct 166 ms 268052 KB Output is correct
12 Correct 677 ms 285436 KB Output is correct
13 Correct 770 ms 288760 KB Output is correct
14 Correct 727 ms 288852 KB Output is correct
15 Correct 484 ms 281720 KB Output is correct
16 Correct 470 ms 281848 KB Output is correct
17 Correct 487 ms 282040 KB Output is correct
18 Correct 471 ms 281592 KB Output is correct
19 Correct 464 ms 281848 KB Output is correct
20 Correct 425 ms 279800 KB Output is correct
21 Correct 187 ms 270200 KB Output is correct
22 Correct 560 ms 283896 KB Output is correct
23 Correct 575 ms 284536 KB Output is correct
24 Correct 579 ms 285048 KB Output is correct
25 Correct 600 ms 285848 KB Output is correct
26 Correct 591 ms 286712 KB Output is correct
27 Correct 699 ms 288760 KB Output is correct
28 Correct 755 ms 288820 KB Output is correct
29 Correct 718 ms 288760 KB Output is correct
30 Correct 416 ms 279928 KB Output is correct
31 Correct 675 ms 288888 KB Output is correct
32 Correct 409 ms 279856 KB Output is correct
33 Correct 393 ms 280880 KB Output is correct
34 Correct 449 ms 282356 KB Output is correct
35 Correct 438 ms 281080 KB Output is correct
36 Correct 431 ms 279928 KB Output is correct
37 Correct 341 ms 277496 KB Output is correct
38 Correct 337 ms 279800 KB Output is correct
39 Correct 473 ms 283256 KB Output is correct
40 Correct 368 ms 279416 KB Output is correct
41 Correct 353 ms 278576 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 151 ms 266488 KB Output isn't correct
2 Halted 0 ms 0 KB -