Submission #489428

#	Time	Username	Problem	Language	Result	Execution time	Memory
489428		mdn2002	Examination (JOI19_examination)	C++14	100 / 100	675 ms	13996 KiB

examination

#include<bits/stdc++.h>
using namespace std;
int n , q , ans [100005];
vector < pair < pair < int , int > , pair < int , int > > > v;
vector < pair < int , pair < int , int > > > e;
void goo ( int l , int r )
{
    if ( l == r ) return;
    int mid = ( l + r ) / 2;
    vector < int > c;
    for ( int i = mid + 1 ; i <= r ; i ++ )
    {
        int y = e [i] . second . first , id = e [i] . second . second;
        if ( id == 1e9 ) c . push_back ( y );
    }
    sort ( c . begin () , c . end () );
    for ( int i = l ; i <= mid ; i ++ )
    {
        int y = e [i] . second . first , id = e [i] . second . second;
        if ( id != 1e9 ) ans [id] += c . end () - lower_bound ( c . begin () , c . end () , y );
    }
    goo ( l , mid );
    goo ( mid + 1 , r );
}
void go ( int l , int r )
{
    if ( l == r ) return;
    int mid = ( l + r ) / 2;
    e . clear ();
    for ( int i = l ; i <= mid ; i ++ )
    {
        int x = v [i] . first . second , y = v [i] . second . first , id = v [i] . second . second;
        if ( id != 1e9 ) e . push_back ( { x , { y , id } } );
    }
    for ( int i = mid + 1 ; i <= r ; i ++ )
    {
        int x = v [i] . first . second , y = v [i] . second . first , id = v [i] . second . second;
        if ( id == 1e9 ) e . push_back ( { x , { y , id } } );
    }
    sort ( e . begin () , e . end () );
    if ( e . size () ) goo ( 0 , e . size () - 1 );
    go ( l , mid );
    go ( mid + 1 , r );
}
int main()
{
    //freopen ( "fence8.in" , "r" , stdin );
    //freopen ( "fence8.out" , "w" , stdout );
    cin >> n >> q;
    for ( int i = 0 ; i < n ; i ++ )
    {
        int x , y;
        cin >> x >> y;
        v . push_back ( { { x + y , x } , { y , 1e9 } } );
    }
    for ( int i = 0 ; i < q ; i ++ )
    {
        int x , y , z;
        cin >> x >> y >> z;
        v . push_back ( { { z , x } , { y , i + 1 } } );
    }
    sort ( v . begin () , v . end () );
    go ( 0 , v . size () - 1 );
    for ( int i = 1 ; i <= q ; i ++ ) cout << ans [i] << endl;
}
/*
1 1
1 1
1 1 2
*/

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