# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
26566 |
2017-07-03T06:17:39 Z |
model_code |
Golf (JOI17_golf) |
C++11 |
|
4762 ms |
981596 KB |
#include <iostream>
#include <cstdio>
#include <cassert>
#include <vector>
#include <utility>
#include <algorithm>
#include <tuple>
#include <set>
#include <queue>
using namespace std;
const int INF = 1000000010;
const int MAX_N = 100010;
const int SEGSIZE = (1<<18);
const int DEL = 0;
const int ASK = 1;
const int ADD = 2;
const int TATE = 0;
const int YOKO = 1;
typedef tuple<int,int,int> T;
typedef pair<int,int> P;
struct node{
int val;
node *chl, *chr;
node(){}
node( int val ): val(val), chl(NULL), chr(NULL) {}
node( int val, node *chl, node *chr ) : val(val), chl(chl), chr(chr) {}
};
node nodes[45000010];
int np;
int val( node *t ){ return !t ? 0 : t->val; }
node* chl( node *t ){ return !t ? NULL : t->chl; }
node* chr( node *t ){ return !t ? NULL : t->chr; }
node* newnode( int val = 0, node *chl = NULL, node *chr = NULL ){
nodes[np] = node( val , chl , chr );
return &nodes[np++];
}
int add( int x , int id , int l , int r , node *cur ){
if( r - l == 1 ){
if( cur->val == 0 ){
cur->val = id + 1;
return 1;
} else {
return 0;
}
}
int md = ( l + r ) / 2;
int res = 0;
if( x < md ){
if( !chl(cur) ){
cur->chl = newnode();
}
res = add( x , id , l , md , chl(cur) );
} else {
if( !chr(cur) ){
cur->chr = newnode();
}
res = add( x , id , md , r , chr(cur) );
}
cur->val += res;
return res;
}
int search( int a , int b , queue<P> &que, int dir, int dist[], int ndist, int l , int r , node *cur ){
if( r - l == 1 ){
if( cur->val == 0 ){
return 0;
}
if( dist[val(cur)-1] == INF ){
dist[val(cur)-1] = ndist;
que.emplace( dir, val(cur)-1 );
}
cur->val = 0;
return 1;
}
if( val(cur) == 0 ){
return 0;
}
if( b <= l || r <= a ){
return 0;
} else {
int md = ( l + r ) / 2;
int chlr = 0;
int chrr = 0;
if( chl(cur) ){
chlr = search( a , b , que , dir , dist , ndist , l , md , chl(cur) );
}
if( chr(cur) ){
chrr = search( a , b , que , dir , dist , ndist , md , r , chr(cur) );
}
cur->val -= chlr + chrr;
return chlr + chrr;
}
}
void make_nex( vector<node*> &segs, queue<P> &que, int dist[], int ndist, int dir, int a , int b , int x , int l = 0, int r = SEGSIZE, int k = 0 ){
search( a , b , que , dir , dist , ndist , 0 , SEGSIZE , segs[k] );
if( r - l == 1 ){
return;
}
if( x < (r+l)/2 ){
make_nex( segs, que, dist, ndist, dir, a, b, x, l, (l+r)/2, k*2+1 );
} else {
make_nex( segs, que, dist, ndist, dir, a, b, x, (l+r)/2, r, k*2+2 );
}
}
void devide_and_add( vector<node*> &segs, int id, int x, int top, int bottom, int l = 0, int r = SEGSIZE, int k = 0 ){
if( top <= l and r <= bottom ){
add( x , id , 0 , SEGSIZE, segs[k] );
} else if( l < bottom and top < r ){
devide_and_add( segs, id, x, top, bottom, l, (l+r)/2, k*2+1 );
devide_and_add( segs, id, x, top, bottom, (l+r)/2, r, k*2+2 );
}
}
void build_segtree( vector<node*> &segs, vector<T> &vec, int n, int sx, int sy, int tx, int ty, int a[], int b[], int c[], int d[] ){
vector<T> sweep;
sweep.emplace_back( -1, ADD, 0 );
sweep.emplace_back( -1, ADD, SEGSIZE-1 );
sweep.emplace_back( sx, ASK, sy );
sweep.emplace_back( tx, ASK, ty );
for( int i = 0; i < n; i++ ){
sweep.emplace_back( a[i], ADD, c[i] );
sweep.emplace_back( a[i], ADD, d[i] );
sweep.emplace_back( b[i], DEL, c[i] );
sweep.emplace_back( b[i], DEL, d[i] );
sweep.emplace_back( a[i], ASK, c[i] );
sweep.emplace_back( b[i], ASK, c[i] );
}
sort( sweep.begin() , sweep.end() );
set<int> ss;
int cnt = 0;
for( T &q : sweep ){
int x = get<0>(q);
int type = get<1>(q);
int y = get<2>(q);
if( type == ADD ){
ss.insert( y );
} else if( type == DEL ){
assert( ss.find( y ) != ss.end() );
ss.erase( ss.find( y ) );
} else {
auto ite = ss.upper_bound( y );
int bottom = (*ite);
ite--;
int top = (*ite);
vec.emplace_back( x, top, bottom );
devide_and_add( segs, int( vec.size() ) - 1, x, top, bottom+1 );
}
}
}
vector<int> compress( vector<int> v ){
vector<int> ord = v;
sort( ord.begin(), ord.end() );
for( int &a : v ){
a = lower_bound( ord.begin(), ord.end(), a ) - ord.begin() + 1;
}
return v;
}
int sx, sy, tx, ty;
int n;
int a[MAX_N], b[MAX_N], c[MAX_N], d[MAX_N];
vector<int> xs, ys;
vector<T> tate, yoko;
vector<node*> seg_tate, seg_yoko;
int tate_dist[MAX_N*2];
int yoko_dist[MAX_N*2];
queue<P> que;
int main(){
scanf( "%d %d %d %d" , &sx , &sy , &tx , &ty );
xs.push_back( sx );
ys.push_back( sy );
xs.push_back( tx );
ys.push_back( ty );
scanf( "%d" , &n );
for( int i = 0; i < n; i++ ){
scanf( "%d %d %d %d" , &a[i] , &b[i] , &c[i] , &d[i] );
xs.push_back( a[i] );
xs.push_back( b[i] );
ys.push_back( c[i] );
ys.push_back( d[i] );
}
xs = compress( xs );
ys = compress( ys );
sx = xs[0];
sy = ys[0];
tx = xs[1];
ty = ys[1];
for( int i = 0; i < n; i++ ){
a[i] = xs[i*2+2];
b[i] = xs[i*2+3];
c[i] = ys[i*2+2];
d[i] = ys[i*2+3];
}
for( int i = 0; i < SEGSIZE*2-1; i++ ){
seg_tate.push_back( newnode() );
seg_yoko.push_back( newnode() );
}
build_segtree( seg_tate, tate, n, sx, sy, tx, ty, a, b, c, d );
build_segtree( seg_yoko, yoko, n, sy, sx, ty, tx, c, d, a, b );
for( int i = 0; i < tate.size(); i++ ){
if( get<0>( tate[i] ) == sx and get<1>( tate[i] ) <= sy and sy <= get<2>( tate[i] ) ){
que.emplace( TATE, i );
tate_dist[i] = 1;
} else {
tate_dist[i] = INF;
}
}
for( int i = 0; i < yoko.size(); i++ ){
if( get<0>( yoko[i] ) == sy and get<1>( yoko[i] ) <= sx and sx <= get<2>( yoko[i] ) ){
que.emplace( YOKO, i );
yoko_dist[i] = 1;
} else {
yoko_dist[i] = INF;
}
}
while( not que.empty() ){
int type = que.front().first;
int id = que.front().second;
que.pop();
if( type == TATE ){
int x = get<0>( tate[id] );
int t = get<1>( tate[id] );
int b = get<2>( tate[id] );
if( x == tx and t <= ty and ty <= b ){
printf( "%d\n" , tate_dist[id] );
return 0;
}
make_nex( seg_yoko, que, yoko_dist, tate_dist[id]+1, YOKO, t, b, x );
}
if( type == YOKO ){
int x = get<0>( yoko[id] );
int t = get<1>( yoko[id] );
int b = get<2>( yoko[id] );
if( x == ty and t <= tx and tx <= b ){
printf( "%d\n" , yoko_dist[id] );
return 0;
}
make_nex( seg_tate, que, tate_dist, yoko_dist[id]+1, TATE, t, b, x );
}
}
assert( false );
return 0;
}
Compilation message
golf.cpp: In function 'void build_segtree(std::vector<node*>&, std::vector<std::tuple<int, int, int> >&, int, int, int, int, int, int*, int*, int*, int*)':
golf.cpp:142:7: warning: unused variable 'cnt' [-Wunused-variable]
int cnt = 0;
^~~
golf.cpp: In function 'int main()':
golf.cpp:224:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int i = 0; i < tate.size(); i++ ){
~~^~~~~~~~~~~~~
golf.cpp:233:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int i = 0; i < yoko.size(); i++ ){
~~^~~~~~~~~~~~~
golf.cpp:188:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf( "%d %d %d %d" , &sx , &sy , &tx , &ty );
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:193:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf( "%d" , &n );
~~~~~^~~~~~~~~~~~~
golf.cpp:195:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf( "%d %d %d %d" , &a[i] , &b[i] , &c[i] , &d[i] );
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
33404 KB |
Output is correct |
2 |
Correct |
34 ms |
33280 KB |
Output is correct |
3 |
Correct |
37 ms |
33488 KB |
Output is correct |
4 |
Correct |
43 ms |
33724 KB |
Output is correct |
5 |
Correct |
49 ms |
37160 KB |
Output is correct |
6 |
Correct |
58 ms |
37148 KB |
Output is correct |
7 |
Correct |
49 ms |
36892 KB |
Output is correct |
8 |
Correct |
61 ms |
37136 KB |
Output is correct |
9 |
Correct |
49 ms |
37276 KB |
Output is correct |
10 |
Correct |
47 ms |
37272 KB |
Output is correct |
11 |
Correct |
47 ms |
37244 KB |
Output is correct |
12 |
Correct |
51 ms |
37156 KB |
Output is correct |
13 |
Correct |
65 ms |
37016 KB |
Output is correct |
14 |
Correct |
48 ms |
37284 KB |
Output is correct |
15 |
Correct |
40 ms |
34180 KB |
Output is correct |
16 |
Correct |
43 ms |
35364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
33404 KB |
Output is correct |
2 |
Correct |
34 ms |
33280 KB |
Output is correct |
3 |
Correct |
37 ms |
33488 KB |
Output is correct |
4 |
Correct |
43 ms |
33724 KB |
Output is correct |
5 |
Correct |
49 ms |
37160 KB |
Output is correct |
6 |
Correct |
58 ms |
37148 KB |
Output is correct |
7 |
Correct |
49 ms |
36892 KB |
Output is correct |
8 |
Correct |
61 ms |
37136 KB |
Output is correct |
9 |
Correct |
49 ms |
37276 KB |
Output is correct |
10 |
Correct |
47 ms |
37272 KB |
Output is correct |
11 |
Correct |
47 ms |
37244 KB |
Output is correct |
12 |
Correct |
51 ms |
37156 KB |
Output is correct |
13 |
Correct |
65 ms |
37016 KB |
Output is correct |
14 |
Correct |
48 ms |
37284 KB |
Output is correct |
15 |
Correct |
40 ms |
34180 KB |
Output is correct |
16 |
Correct |
43 ms |
35364 KB |
Output is correct |
17 |
Correct |
48 ms |
37556 KB |
Output is correct |
18 |
Correct |
47 ms |
37668 KB |
Output is correct |
19 |
Correct |
45 ms |
37536 KB |
Output is correct |
20 |
Correct |
50 ms |
37592 KB |
Output is correct |
21 |
Correct |
51 ms |
37860 KB |
Output is correct |
22 |
Correct |
50 ms |
37792 KB |
Output is correct |
23 |
Correct |
44 ms |
37540 KB |
Output is correct |
24 |
Correct |
52 ms |
37680 KB |
Output is correct |
25 |
Correct |
42 ms |
37552 KB |
Output is correct |
26 |
Correct |
50 ms |
37408 KB |
Output is correct |
27 |
Correct |
37 ms |
34440 KB |
Output is correct |
28 |
Correct |
42 ms |
35612 KB |
Output is correct |
29 |
Correct |
46 ms |
35624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
33404 KB |
Output is correct |
2 |
Correct |
34 ms |
33280 KB |
Output is correct |
3 |
Correct |
37 ms |
33488 KB |
Output is correct |
4 |
Correct |
43 ms |
33724 KB |
Output is correct |
5 |
Correct |
49 ms |
37160 KB |
Output is correct |
6 |
Correct |
58 ms |
37148 KB |
Output is correct |
7 |
Correct |
49 ms |
36892 KB |
Output is correct |
8 |
Correct |
61 ms |
37136 KB |
Output is correct |
9 |
Correct |
49 ms |
37276 KB |
Output is correct |
10 |
Correct |
47 ms |
37272 KB |
Output is correct |
11 |
Correct |
47 ms |
37244 KB |
Output is correct |
12 |
Correct |
51 ms |
37156 KB |
Output is correct |
13 |
Correct |
65 ms |
37016 KB |
Output is correct |
14 |
Correct |
48 ms |
37284 KB |
Output is correct |
15 |
Correct |
40 ms |
34180 KB |
Output is correct |
16 |
Correct |
43 ms |
35364 KB |
Output is correct |
17 |
Correct |
48 ms |
37556 KB |
Output is correct |
18 |
Correct |
47 ms |
37668 KB |
Output is correct |
19 |
Correct |
45 ms |
37536 KB |
Output is correct |
20 |
Correct |
50 ms |
37592 KB |
Output is correct |
21 |
Correct |
51 ms |
37860 KB |
Output is correct |
22 |
Correct |
50 ms |
37792 KB |
Output is correct |
23 |
Correct |
44 ms |
37540 KB |
Output is correct |
24 |
Correct |
52 ms |
37680 KB |
Output is correct |
25 |
Correct |
42 ms |
37552 KB |
Output is correct |
26 |
Correct |
50 ms |
37408 KB |
Output is correct |
27 |
Correct |
37 ms |
34440 KB |
Output is correct |
28 |
Correct |
42 ms |
35612 KB |
Output is correct |
29 |
Correct |
46 ms |
35624 KB |
Output is correct |
30 |
Correct |
2558 ms |
942016 KB |
Output is correct |
31 |
Correct |
3182 ms |
954516 KB |
Output is correct |
32 |
Correct |
4035 ms |
923112 KB |
Output is correct |
33 |
Correct |
4762 ms |
939876 KB |
Output is correct |
34 |
Correct |
3150 ms |
981596 KB |
Output is correct |
35 |
Correct |
4438 ms |
969012 KB |
Output is correct |
36 |
Correct |
2430 ms |
945912 KB |
Output is correct |
37 |
Correct |
3712 ms |
922800 KB |
Output is correct |
38 |
Correct |
3185 ms |
966732 KB |
Output is correct |
39 |
Correct |
3930 ms |
928676 KB |
Output is correct |
40 |
Correct |
447 ms |
74772 KB |
Output is correct |
41 |
Correct |
422 ms |
74712 KB |
Output is correct |
42 |
Correct |
419 ms |
74952 KB |
Output is correct |
43 |
Correct |
457 ms |
75056 KB |
Output is correct |
44 |
Correct |
442 ms |
75252 KB |
Output is correct |
45 |
Correct |
479 ms |
75324 KB |
Output is correct |
46 |
Correct |
428 ms |
75304 KB |
Output is correct |
47 |
Correct |
474 ms |
75284 KB |
Output is correct |
48 |
Correct |
457 ms |
75328 KB |
Output is correct |
49 |
Correct |
442 ms |
75440 KB |
Output is correct |
50 |
Correct |
43 ms |
35492 KB |
Output is correct |
51 |
Correct |
44 ms |
35632 KB |
Output is correct |
52 |
Correct |
46 ms |
35620 KB |
Output is correct |