Submission #543598

#	Time	Username	Problem	Language	Result	Execution time	Memory
543598		chonka	Examination (JOI19_examination)	C++98	100 / 100	148 ms	12200 KiB

examination

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;

// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define MAXN 100007

int n , q ;

struct el {
    int x , y , sm , id ;
};

el a[ MAXN ] , qlist[ MAXN ] ;
int ans[ MAXN ] ;
vector < pair < int , int > > srtx , srty ;
int posx[ MAXN ] , posy[ MAXN ] ;

class fenw {
public :
    int tr[ MAXN ] ;
    void init ( ) {
        for ( int i = 0 ; i <= n ; ++ i ) {
            tr[ i ] = 0 ;
        }
    }
    void update ( int pos , int add ) {
        for ( int i = pos ; i <= n ; i += ( i & ( -i ) ) ) {
            tr[ i ] += add ;
        }
    }
    int query ( int pos ) {
        int ans = 0 ;
        for ( int i = pos ; i > 0 ; i -= ( i & ( -i ) ) ) {
            ans += tr[ i ] ;
        }
        return ans ;
    }
};
fenw w ;

int get_fst ( vector < pair < int , int > > &wh , int sr ) {
    int l , r , mid ;
    l = 0 , r = n - 1 ;
    if ( wh[ r ].first < sr ) { return n ; }
    while ( r - l > 3 ) {
        mid = ( l + r ) / 2 ;
        if ( wh[ mid ].first >= sr ) { r = mid ; }
        else { l = mid ; }
    }
    while ( wh[ l ].first < sr ) { ++ l ; }
    return l ;
}

void input ( ) {
    cin >> n >> q ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ].x >> a[ i ].y ;
        a[ i ].sm = a[ i ].x + a[ i ].y ;
        a[ i ].id = i ;
        srtx.push_back ( { a[ i ].x , i } ) ;
        srty.push_back ( { a[ i ].y , i } ) ;
    }
    sort ( srtx.begin ( ) , srtx.end ( ) ) ;
    sort ( srty.begin ( ) , srty.end ( ) ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        posx[ srtx[ i - 1 ].second ] = i ;
        posy[ srty[ i - 1 ].second ] = i ;
    }
    for ( int i = 1 ; i <= q ; ++ i ) {
        cin >> qlist[ i ].x >> qlist[ i ].y >> qlist[ i ].sm ;
        qlist[ i ].id = i ;
    }
}

void solve ( ) {
    auto cmp_x = [ & ] ( el p1 , el p2 ) {
        return ( p1.x > p2.x ) ;
    };
    auto cmp_sm = [ & ] ( el p1 , el p2 ) {
        return ( p1.sm > p2.sm ) ;
    };
    sort ( qlist + 1 , qlist + q + 1 , cmp_x ) ;
    sort ( a + 1 , a + n + 1 , cmp_x ) ;
    int pos = 0 ;
    w.init ( ) ;
    for ( int i = 1 ; i <= q ; ++ i ) {
        while ( pos + 1 <= n && a[ pos + 1 ].x >= qlist[ i ].x ) {
            w.update ( posy[ a[ pos + 1 ].id ] , 1 ) ;
            ++ pos ;
        }
        if ( qlist[ i ].x + qlist[ i ].y >= qlist[ i ].sm ) {
            int en = get_fst ( srty , qlist[ i ].y ) ;
            ans[ qlist[ i ].id ] = pos - w.query ( en ) ;
        }
    }
    sort ( qlist + 1 , qlist + q + 1 , cmp_sm ) ;
    sort ( a + 1 , a + n + 1 , cmp_sm ) ;
    w.init ( ) , pos = 0 ;
    for ( int i = 1 ; i <= q ; ++ i ) {
        while ( pos + 1 <= n && a[ pos + 1 ].sm >= qlist[ i ].sm ) {
            w.update ( posx[ a[ pos + 1 ].id ] , 1 ) ;
            ++ pos ;
        }
        if ( qlist[ i ].x + qlist[ i ].y <= qlist[ i ].sm ) {
            ans[ qlist[ i ].id ] = pos ;
            int en = get_fst ( srtx , qlist[ i ].x ) ;
            ans[ qlist[ i ].id ] -= w.query ( en ) ;
        }
    }
    w.init ( ) , pos = 0 ;
    for ( int i = 1 ; i <= q ; ++ i ) {
        while ( pos + 1 <= n && a[ pos + 1 ].sm >= qlist[ i ].sm ) {
            w.update ( posy[ a[ pos + 1 ].id ] , 1 ) ;
            ++ pos ;
        }
        if ( qlist[ i ].x + qlist[ i ].y <= qlist[ i ].sm ) {
            int en = get_fst ( srty , qlist[ i ].y ) ;
            ans[ qlist[ i ].id ] -= w.query ( en ) ;
        }
    }
    for ( int i = 1 ; i <= q ; ++ i ) {
        cout << ans[ i ] << "\n" ;
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ;
    // cin >> t ;
    while ( t -- ) {
        input ( ) ;
        solve ( ) ;
    }
    return 0 ;
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57