Submission #263421

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
263421	2020-08-13T16:50:20 Z	CaroLinda	New Home (APIO18_new_home)	C++14	10 / 100	594 ms	55532 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	14 ms	14720 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	14 ms	14720 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	544 ms	48736 KB	Output is correct
2	Correct	480 ms	46392 KB	Output is correct
3	Correct	594 ms	55488 KB	Output is correct
4	Correct	557 ms	49476 KB	Output is correct
5	Correct	556 ms	50336 KB	Output is correct
6	Correct	468 ms	46288 KB	Output is correct
7	Correct	494 ms	55532 KB	Output is correct
8	Correct	507 ms	49200 KB	Output is correct
9	Correct	519 ms	47872 KB	Output is correct
10	Correct	489 ms	47236 KB	Output is correct
11	Correct	439 ms	46116 KB	Output is correct
12	Correct	455 ms	47032 KB	Output is correct