Submission #32009

#	Time	Username	Problem	Language	Result	Execution time	Memory
32009		chonka	trapezoid (balkan11_trapezoid)	C++98	100 / 100	393 ms	52616 KiB

trapezoid

#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 (stderr)

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]
     }
     ^

• Subtask 1: 100 / 100