#include<iostream>
#include<stdio.h>
#include<vector>
#include<map>
#include<algorithm>
using namespace std ;
#define MAXN 100007
#define MOD 30013
pair < int , int > dp[ MAXN ] ;
int n ;
struct tuhla {
int x , y , z , t ;
tuhla ( ) {
x = y = z = t = 0 ;
}
tuhla ( int _x , int _y , int _t , int _z ) {
x = _x ;
y = _y ;
z = _z ;
t = _t ;
}
bool operator < ( tuhla other ) {
if ( x != other.x ) { return ( x < other.x ) ; }
if ( y != other.y ) { return ( y < other.y ) ; }
}
};
struct upd {
int pos ;
int val ;
int ways ;
upd ( ) { pos = val = ways = 0 ; }
upd ( int _pos , int _val , int _ways ) {
pos = _pos ;
val = _val ;
ways = _ways ;
}
};
vector < upd > to_upd[ 3 * MAXN ] ;
tuhla a[ MAXN ] ;
vector < int > srt1 , srt2 ;
map < int , int > ZX ;
vector < tuhla > st[ 4 * MAXN ] ;
vector < tuhla > en[ 4 * MAXN ] ;
class Tree {
public :
pair < int , int > tr[ 10 * MAXN ] ;
void init ( int where , int IL , int IR ) {
tr[ where ].first = 0 ;
tr[ where ].second = 0 ;
if ( IL == IR ) { return ; }
int mid = ( IL + IR ) / 2 ;
init ( 2 * where , IL , mid ) ;
init ( 2 * where + 1 , mid + 1 , IR ) ;
}
pair < int , int > unite ( pair < int , int > l , pair < int , int > r ) {
pair < int , int > ret ;
if ( l.first > r.first ) {
ret = l ;
}
else if ( l.first < r.first ) {
ret = r ;
}
else {
ret = l ;
ret.second += r.second ;
ret.second %= MOD ;
}
return ret ;
}
void update ( int where , int IL , int IR , int pos , int x , long long y ) {
if ( IR < pos || pos < IL ) { return ; }
if ( IL == IR ) {
if ( tr[ where ].first < x ) {
tr[ where ].first = x ;
tr[ where ].second = 0 ;
}
if ( tr[ where ].first == x ) {
tr[ where ].second += y ;
tr[ where ].second %= MOD ;
}
return ;
}
int mid = ( IL + IR ) / 2 ;
update ( 2 * where , IL , mid , pos , x , y ) ;
update ( 2 * where + 1 , mid + 1 , IR , pos , x , y ) ;
tr[ where ] = unite ( tr[ 2 * where ] , tr[ 2 * where + 1 ] ) ;
}
pair < int , int > query ( int where , int IL , int IR , int CURL , int CURR ) {
if ( IR < CURL || CURR < IL ) { return make_pair ( 0 , 0 ) ; }
if ( CURL <= IL && IR <= CURR ) {
return tr[ where ] ;
}
int mid = ( IL + IR ) / 2 ;
return ( unite ( query ( 2 * where , IL , mid , CURL , CURR ) , query ( 2 * where + 1 , mid + 1 , IR , CURL , CURR ) ) ) ;
}
};
Tree w ;
void compress ( ) {
sort ( srt1.begin ( ) , srt1.end ( ) ) ;
sort ( srt2.begin ( ) , srt2.end ( ) ) ;
int id = 1 ;
int i ;
for ( i = 0 ; i < 2 * n ; i ++ ) {
if ( i != 0 && ( srt1[ i ] == srt1[ i - 1 ] ) ) { continue ; }
ZX[ srt1[ i ] ] = id ;
id ++ ;
}
for ( i = 1 ; i <= n ; i ++ ) {
a[ i ].x = ZX[ a[ i ].x ] ;
a[ i ].y = ZX[ a[ i ].y ] ;
}
ZX.clear ( ) ;
id = 1 ;
for ( i = 0 ; i < 2 * n ; i ++ ) {
if ( i != 0 && ( srt2[ i ] == srt2[ i - 1 ] ) ) { continue ; }
ZX[ srt2[ i ] ] = id ;
id ++ ;
}
for ( i = 1 ; i <= n ; i ++ ) {
a[ i ].t = ZX[ a[ i ].t ] ;
a[ i ].z = ZX[ a[ i ].z ] ;
}
}
void input ( ) {
scanf ( "%d" , &n ) ;
int i ;
for ( i = 1 ; i <= n ; i ++ ) {
scanf ( "%d%d%d%d" , &a[ i ].x , &a[ i ].y , &a[ i ].z , &a[ i ].t ) ;
srt1.push_back ( a[ i ].x ) ;
srt1.push_back ( a[ i ].y ) ;
srt2.push_back ( a[ i ].t ) ;
srt2.push_back ( a[ i ].z ) ;
}
compress ( ) ;
}
void solve ( ) {
w.init ( 1 , 1 , 2 * n ) ;
sort ( a + 1 , a + n + 1 ) ;
int i ;
int j = 1 ;
int t ;
pair < int , int > ans ;
ans.first = ans.second = 0 ;
for ( i = 1 ; i <= n ; i ++ ) {
while ( j <= a[ i ].x ) {
int sz = to_upd[ j ].size ( ) ;
for ( t = 0 ; t < sz ; t ++ ) {
w.update ( 1 , 1 , 2 * n , to_upd[ j ][ t ].pos , to_upd[ j ][ t ].val , to_upd[ j ][ t ].ways ) ;
}
j ++ ;
}
pair < int , int > ret = w.query ( 1 , 1 , 2 * n , 1 , a[ i ].z ) ;
ret.first ++ ;
if ( ret.second < 1 ) { ret.second = 1 ; }
dp[ i ] = ret ;
to_upd[ a[ i ].y ].push_back ( upd ( a[ i ].t , ret.first , ret.second ) ) ;
ans = w.unite ( ans , ret ) ;
}
printf ( "%d %d\n" , ans.first , ans.second ) ;
}
int main ( ) {
input ( ) ;
solve ( ) ;
return 0 ;
}
Compilation message
trapezoid.cpp: In function 'void input()':
trapezoid.cpp:139:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ( "%d" , &n ) ;
^
trapezoid.cpp:142:78: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ( "%d%d%d%d" , &a[ i ].x , &a[ i ].y , &a[ i ].z , &a[ i ].t ) ;
^
trapezoid.cpp: In member function 'bool tuhla::operator<(tuhla)':
trapezoid.cpp:28:5: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
37992 KB |
Output is correct |
| 2 |
Correct |
9 ms |
37992 KB |
Output is correct |
| 3 |
Correct |
13 ms |
38124 KB |
Output is correct |
| 4 |
Correct |
9 ms |
38124 KB |
Output is correct |
| 5 |
Correct |
9 ms |
38256 KB |
Output is correct |
| 6 |
Correct |
13 ms |
38416 KB |
Output is correct |
| 7 |
Correct |
16 ms |
38548 KB |
Output is correct |
| 8 |
Correct |
19 ms |
38812 KB |
Output is correct |
| 9 |
Correct |
43 ms |
39472 KB |
Output is correct |
| 10 |
Correct |
66 ms |
41048 KB |
Output is correct |
| 11 |
Correct |
79 ms |
41708 KB |
Output is correct |
| 12 |
Correct |
163 ms |
45256 KB |
Output is correct |
| 13 |
Correct |
229 ms |
46576 KB |
Output is correct |
| 14 |
Correct |
273 ms |
48788 KB |
Output is correct |
| 15 |
Correct |
316 ms |
49448 KB |
Output is correct |
| 16 |
Correct |
366 ms |
50108 KB |
Output is correct |
| 17 |
Correct |
356 ms |
50636 KB |
Output is correct |
| 18 |
Correct |
339 ms |
51296 KB |
Output is correct |
| 19 |
Correct |
343 ms |
51956 KB |
Output is correct |
| 20 |
Correct |
393 ms |
52616 KB |
Output is correct |
