Submission #32009

# Submission time Handle Problem Language Result Execution time Memory
32009 2017-09-21T21:42:44 Z chonka trapezoid (balkan11_trapezoid) C++
100 / 100
393 ms 52616 KB
#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