| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 135812 |
2019-07-24T11:44:55 Z |
model_code |
Walk (CEOI06_walk) |
C++17 |
|
217 ms |
12760 KB |
#include <algorithm>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct prepreka {
int x1, y1, x2, y2;
int x;
int index;
int link1, link2;
};
int cmp_x2( const prepreka &A, const prepreka B ) { return A.x2 < B.x2; }
int cmp_y1( const prepreka &A, const prepreka B ) { return A.y1 < B.y1; }
int cmp_y2( const prepreka &A, const prepreka B ) { return A.y2 > B.y2; }
int cmp_index( const prepreka &A, const prepreka B ) { return A.index < B.index; }
int n;
int X, Y;
vector<prepreka> A;
const int inf = 1000000000;
void input() {
scanf( "%d%d", &X, &Y );
scanf( "%d", &n );
for( int i = 0; i < n; ++i ) {
prepreka P;
scanf( "%d%d%d%d", &P.x1, &P.y1, &P.x2, &P.y2 );
if( P.x1 > P.x2 ) swap( P.x1, P.x2 );
if( P.y1 > P.y2 ) swap( P.y1, P.y2 );
A.push_back( P );
}
}
struct event {
int index, y, type;
event( int I, int Y, int T ) { index = I; y = Y; type = T; }
};
int cmp_event( const event &A, const event &B ) {
if( A.y != B.y ) return A.y < B.y;
return A.type < B.type;
}
struct tournament_tree {
vector<int> a;
int offset;
tournament_tree( int N ) {
for( offset = 1; offset < N; offset *= 2 );
a.resize( 2*offset );
for( int i = 0; i < 2*offset; ++i ) a[i] = -1;
}
void insert( int x, int val ) {
if( a[offset+x] != -1 ) return;
for( int i = offset+x; i; i >>= 1 )
a[i] = std::max(a[i], val);
}
void erase( int x ) {
a[offset+x] = -1;
for( int i = (offset+x)>>1; i; i >>= 1 )
a[i] = std::max(a[2*i], a[2*i+1]);
}
int rec( int x, int i, int lo, int hi ) {
if( hi <= x ) return a[i];
if( lo >= x ) return -1;
int mid = (lo+hi)/2;
return std::max(rec( x, 2*i, lo, mid ), rec( x, 2*i+1, mid, hi ));
}
int query( int x ) {
return rec( x, 1, 0, offset );
}
};
void init() {
int N = 0;
{
int I = 0;
int lastx = -1;
sort( A.begin(), A.end(), cmp_x2 );
for( vector<prepreka>::iterator P = A.begin(); P != A.end(); ++P ) {
P->index = I++;
P->link1 = P->link2 = -1;
if( P->x2 != lastx ) ++N;
P->x = N;
lastx = P->x2;
}
}
{
int x = 0, y = 0;
sort( A.begin(), A.end(), cmp_y1 );
for( vector<prepreka>::iterator P = A.begin(); P != A.end(); ++P ) {
if( P->y1 > y && P->x1 <= x && x <= P->x2 ) {
x = P->x2+1;
y = P->y1;
P->y2 = inf;
}
}
}
{
int x = 0, y = 0;
sort( A.begin(), A.end(), cmp_y2 );
for( vector<prepreka>::iterator P = A.begin(); P != A.end(); ++P ) {
if( P->y2 < y && P->x1 <= x && x <= P->x2 ) {
x = P->x2+1;
y = P->y2;
P->y1 = -inf;
}
}
}
sort( A.begin(), A.end(), cmp_index );
vector<event> E;
for( vector<prepreka>::iterator P = A.begin(); P != A.end(); ++P ) {
E.push_back( event( P->index, P->y1, 0 ) );
E.push_back( event( P->index, P->y1-1, 1 ) );
E.push_back( event( P->index, P->y2+1, 2 ) );
E.push_back( event( P->index, P->y2, 3 ) );
}
tournament_tree T( N+1 );
sort( E.begin(), E.end(), cmp_event );
for( vector<event>::iterator e = E.begin(); e != E.end(); ++e ) {
if( e->type == 0 ) T.insert( A[e->index].x, e->index );
if( e->type == 1 ) A[e->index].link1 = T.query( A[e->index].x );
if( e->type == 2 ) A[e->index].link2 = T.query( A[e->index].x );
if( e->type == 3 ) T.erase( A[e->index].x );
}
}
typedef long long llint;
vector< pair<llint,llint> > dp;
vector< pair<int,int> > solution;
void backtrack( llint &val, int &link ) {
if( link == -1 ) {
solution.push_back( pair<int,int> (X, 0) ); X = 0;
solution.push_back( pair<int,int> (0, Y) ); Y = 0;
} else {
if( val == X-A[link].x2-1 + abs( Y - A[link].y1+1 ) + dp[link].first ) {
int dx = X - A[link].x2-1;
int dy = Y - A[link].y1+1;
if( dx ) { solution.push_back( pair<int,int> (dx, 0) ); X -= dx; }
if( dy ) { solution.push_back( pair<int,int> (0, dy) ); Y -= dy; }
val = dp[link].first;
link = A[link].link1;
} else {
int dx = X - A[link].x2-1;
int dy = Y - A[link].y2-1;
if( dx ) { solution.push_back( pair<int,int> (dx, 0) ); X -= dx; }
if( dy ) { solution.push_back( pair<int,int> (0, dy) ); Y -= dy; }
val = dp[link].second;
link = A[link].link2;
}
}
}
void solve() {
dp.resize( n );
for( int i = 0; i < n; ++i ) {
{
int j = A[i].link1;
if( j == -1 ) dp[i].first = A[i].x2+1 + abs( A[i].y1-1 );
else dp[i].first =
std::min(A[i].x2-A[j].x2 + abs( A[i].y1-1 - A[j].y1+1 ) + dp[j].first,
A[i].x2-A[j].x2 + abs( A[i].y1-1 - A[j].y2-1 ) + dp[j].second);
}
{
int j = A[i].link2;
if( j == -1 ) dp[i].second = A[i].x2+1 + abs( A[i].y2+1 );
else dp[i].second =
std::min(A[i].x2-A[j].x2 + abs( A[i].y2+1 - A[j].y1+1 ) + dp[j].first,
A[i].x2-A[j].x2 + abs( A[i].y2+1 - A[j].y2-1 ) + dp[j].second);
}
}
int link = -1;
for( int i = n-1; i >= 0; --i )
if( A[i].x2 < X && A[i].y1 <= Y && Y <= A[i].y2 ) {
link = A[i].index;
break;
}
long long ret = X + abs(Y);
if( link != -1 )
ret =
std::min(X-A[link].x2-1 + abs( Y - A[link].y1+1 ) + dp[link].first,
X-A[link].x2-1 + abs( Y - A[link].y2-1 ) + dp[link].second);
printf( "%lld\n", ret );
while( X != 0 || Y != 0 ) backtrack( ret, link );
printf( "%d\n", solution.size() );
for( int i = solution.size()-1; i >= 0; --i )
printf( "%d %d\n", solution[i].first, solution[i].second );
}
int main( void ) {
input();
init();
solve();
return 0;
}
Compilation message
walk.cpp: In function 'void solve()':
walk.cpp:196:36: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' [-Wformat=]
printf( "%d\n", solution.size() );
~~~~~~~~~~~~~~~ ^
walk.cpp: In function 'void input()':
walk.cpp:26:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf( "%d%d", &X, &Y );
~~~~~^~~~~~~~~~~~~~~~~~
walk.cpp:27:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf( "%d", &n );
~~~~~^~~~~~~~~~~~
walk.cpp:30:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf( "%d%d%d%d", &P.x1, &P.y1, &P.x2, &P.y2 );
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Correct |
3 ms |
504 KB |
Output is correct |
| 5 |
Correct |
186 ms |
12256 KB |
Output is correct |
| 6 |
Correct |
59 ms |
3560 KB |
Output is correct |
| 7 |
Correct |
113 ms |
6476 KB |
Output is correct |
| 8 |
Correct |
217 ms |
12656 KB |
Output is correct |
| 9 |
Correct |
205 ms |
12636 KB |
Output is correct |
| 10 |
Correct |
206 ms |
12760 KB |
Output is correct |
