Submission #263421

#	Time	Username	Problem	Language	Result	Execution time	Memory
263421		CaroLinda	New Home (APIO18_new_home)	C++14	10 / 100	594 ms	55532 KiB

new_home

/*

Playing the sand
Holding your hand
Cause I remember every sunset
I remember every word you said
*/

#include <bits/stdc++.h>

#define lp(i,a,b) for(int i = a; i < b ; i++)
#define ff first
#define ss second
#define pb emplace_back
#define ll long long
#define mk make_pair
#define sz(x) (int)(x.size())
#define pii pair<int,int>
#define mkt make_tuple
#define debug 
#define all(x) x.begin(),x.end()

const int MAX = 3e5+10 ;
const int MAX_COORD = 1e8+10 ;

using namespace std ;

struct Event
{
    int type , x, id , xIntercept ;

    Event(int type = 0 , int x = 0 , int id = 0  , int xIntercept = 0 ) : type(type) , x(x) , id(id) , xIntercept(xIntercept) {}
    bool operator < (Event other) const
    {

        if(x == other.x ) return type < other.type ;
        return x < other.x ;

    }

};

int N , K , Q ;
int mxNegative, mnPositive  = MAX_COORD ;
int ansQuery[MAX] ;
vector<int> store[MAX] ;
vector< pair<int,int> > lines ;
vector<Event> sweepPositive, sweepNegative ;

void add(int slope , int beg, int en  )
{

    debug("Adding the so-called line %d %d %d\n" , slope , beg, en ) ;

    if( slope == -1 ) sweepNegative.emplace_back( Event(0, beg , 0 , en) ) ;
    else sweepPositive.emplace_back( Event(1,en , 0 , beg ) ) ;

}

void impossible()
{
    for(int i = 1 ; i <= Q ; i++ ) printf("-1\n") ;
    exit(0) ;
}

int main()
{

    scanf("%d%d%d", &N , &K , &Q  );
    for(int i = 1 ; i <= N ; i++ )
    {
        int location , shop , year1, year2 ;

        scanf("%d%d%d%d", &location , &shop, &year1, &year2 ) ;

        assert( year1 == 1 && year2 == 100000000 ) ;

        store[ shop ].emplace_back( location ) ;

    }

    for(int i = 1 , x , year ; i <= Q ; i++ )
    {

        scanf("%d%d", &x, &year ) ;

        sweepNegative.emplace_back( Event(1,x,i, 0) ) ;
        sweepPositive.emplace_back( Event(0, x, i, 0) ) ;

    }

    for(int i = 1 ; i <= K ; i++ )
    {
        if( sz(store[i]) == 0  ) impossible() ;

        sort( all(store[i]) ) ;
        int storeSize = sz(store[i]) ;

        //Let's add all negative slopes first
        add( -1 , -1 , store[i][0] ) ;
        for(int j = 1 ; j < sz(store[i]) ; j++ )
            add(-1, ceil( (1.0*store[i][j] + 1.0*store[i][j-1])/2.0 ) , store[i][j] ) ;

        //Now let's add positive slopes
        add(1, store[i][ storeSize-1 ] , MAX_COORD) ;
        for(int j = storeSize-2 ; j >= 0 ; j-- )
            add(1,  store[i][j] , (store[i][j]+store[i][j+1])/2 ) ;

    }

    sort( all(sweepNegative) ) ;
    sort( all(sweepPositive) ) ;
    reverse( all(sweepPositive) ) ;

    for(auto e : sweepNegative)
    {
        if( e.type == 0 )
        {
            mxNegative = max( mxNegative, e.xIntercept ) ;
            continue ;
        }

        ansQuery[ e.id ] = max( ansQuery[e.id] , mxNegative - e.x ) ;

    }

    for(auto e : sweepPositive )
    {

        if( e.type == 1 )
        {
            mnPositive = min( mnPositive, e.xIntercept ) ;
            continue ;
        }

        ansQuery[e.id] = max( ansQuery[e.id] , e.x - mnPositive ) ;

    }

    for(int i = 1 ; i <=  Q ; i++ ) printf("%d\n", ansQuery[i] ) ;

}

Compilation message (stderr)

new_home.cpp: In function 'void add(int, int, int)':
new_home.cpp:53:11: warning: left operand of comma operator has no effect [-Wunused-value]
   53 |     debug("Adding the so-called line %d %d %d\n" , slope , beg, en ) ;
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:53:60: warning: right operand of comma operator has no effect [-Wunused-value]
   53 |     debug("Adding the so-called line %d %d %d\n" , slope , beg, en ) ;
      |                                                            ^~~
new_home.cpp:53:65: warning: right operand of comma operator has no effect [-Wunused-value]
   53 |     debug("Adding the so-called line %d %d %d\n" , slope , beg, en ) ;
      |                                                                 ^~
new_home.cpp: In function 'int main()':
new_home.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |     scanf("%d%d%d", &N , &K , &Q  );
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |         scanf("%d%d%d%d", &location , &shop, &year1, &year2 ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |         scanf("%d%d", &x, &year ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 10 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20