Submission #295286

#	Time	Username	Problem	Language	Result	Execution time	Memory
295286		CaroLinda	New Home (APIO18_new_home)	C++14	80 / 100	5098 ms	774320 KiB

new_home

#include <bits/stdc++.h>

static struct FASTIO {

  char READ_CHARACTER; bool REMAINING_CHARACTER = false;

  inline void ignore(); inline void flush();

  template <typename T> inline bool READ_INT(T &x); template <typename T> inline bool READ_STRING(T &x);
  /*                                                          Fast I/O Code Optimizer                                                          */
  template<size_t N> inline bool READ_CHAR_ARRAY(char (&x)[N]); template<size_t N> inline bool READ_VAR(char (&x)[N]);
  /*                    A tool to optimize execution time of C++ codes by replacing methods of reading and writing variables                   */
  template <typename T> inline bool READ_CHAR(T &x); inline bool READ_CHAR_ARRAY(char*& x); inline bool READ_GETLINE(std::string &x);
  /*                                                    Use it on fastio.pythonanywhere.com                                                    */
  template <typename T> inline bool READ_FLOAT(T &x); template <typename T> inline bool READ_DOUBLE(T &x);
  /*                                          Github Project: github.com/bfs07/Fast-IO-Code-Optimizer                                          */
  template<std::size_t N> inline bool READ_BITSET(std::bitset<N> &bit); template<std::size_t N> inline bool READ_VAR(std::bitset<N> &bit);
  inline bool READ_VAR(bool &x); inline bool READ_VAR(short int &x); inline bool READ_VAR(int &x); 
  inline bool READ_VAR(long int &x); inline bool READ_VAR(long long int &x); inline bool READ_VAR(unsigned short int &x);
  inline bool READ_VAR(unsigned int &x); inline bool READ_VAR(unsigned long &x); inline bool READ_VAR(unsigned long long &x);
  inline bool READ_VAR(std::string &x); inline bool READ_VAR(char &x); inline bool READ_VAR(char*& x); inline bool READ_VAR(float &x);
  inline bool READ_VAR(double &x); inline bool READ_VAR(long double &x); template <typename T> inline void WRITE_INT(T x);
  inline void WRITE_STRING(std::string &x); inline void WRITE_CHAR(char x); inline void WRITE_CHAR_ARRAY(const char *x);
  inline void WRITE_FLOAT(float x); template <typename T> inline void WRITE_DOUBLE(T x); inline void WRITE_VAR(bool x);
  inline void WRITE_VAR(short int x); inline void WRITE_VAR(int x); inline void WRITE_VAR(long int x); inline void WRITE_VAR(long long int x);
  inline void WRITE_VAR(unsigned short int x); inline void WRITE_VAR(unsigned int x); inline void WRITE_VAR(unsigned long x);
  inline void WRITE_VAR(unsigned long long x); inline void WRITE_VAR(char x); inline void WRITE_VAR(const char *x); 
  inline void WRITE_VAR(std::string &x); inline void WRITE_VAR(float x); inline void WRITE_VAR(double x); inline void WRITE_VAR(long double x);
  template<std::size_t N> inline void WRITE_VAR(std::bitset<N> &bit); template<std::size_t N> inline void WRITE_BITSET(std::bitset<N> &bit);

} __FIO__;


#include <bits/stdc++.h>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

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

const int MAXN = 3e5+10 ;
const int MAXT = 1e9+10 ;
const int MAX_COORD = 1e9+7 ;

using namespace std ;

struct Event
{
    int xConta, xIntercept, type , t1, t2 ;
    Event(int a=0, int b=0, int c=0, int d=0, int e=0) : xConta(a), xIntercept(b), type(c) , t1(d), t2(e){}

};

int ansQuery[MAXN] ;

struct Seg
{

    int n ;
    vector<Event> tree[MAXN*2] ;

    int m(int l, int r) { return (l+r)>>1 ; }

    void insertEvent(int t1, int t2,  Event e)
    {

        if(e.type > 0)
        {
            for(t1 += n ; t1 >= 1 ; t1 >>= 1)
                tree[t1].pb(e) ;

            return ;
        }

        for(t1 += n , t2 += n ; t1 < t2 ; t1 >>= 1 , t2>>=1 )
        {
            if( t1&1 ) tree[t1].pb(e), t1++ ;
            if( t2&1 ) t2--, tree[t2].pb(e) ;
        }

    }

    void solve(int forbiddenType )
    {
        for(int i = 1 ; i < 2*n ; i++ )
        {
            int mxNegative = -MAXT , mnPositive = MAXT ;

            for(auto e : tree[i])
            {
                if( e.type == forbiddenType ) continue ;
                if( e.type > 0 )
                {
                    int c = (forbiddenType == 0) ? mxNegative - e.xConta : e.xConta-mnPositive ;
                    if( ansQuery[e.type] < c ) ansQuery[e.type] = c ;
                }
                else
                {
                    if(forbiddenType == 0 && e.xIntercept > mxNegative ) mxNegative = e.xIntercept ;
                    else if( mnPositive > e.xIntercept) mnPositive = e.xIntercept ;
                }
            }
        }
    }

} seg ;

 
 

int N , K , Q ;
int timeRight[MAXN] , timeLeft[MAXN] , midRight[MAXN] ,midLeft[MAXN] ;
vector<int> compressionTime , compressionX ;
set<int> lojinhas ;
vector< pii > myVecOfPairs ;
vector<pii> coordX[MAXN] ;
vector<tiii> myStores[MAXN] ;
map< pii , int > segments[MAXN] ;
vector<Event> sweep ;

int maiorIgual(int x)
{

    int l = 0 , r = sz(compressionTime) - 1 , mid , best = r+1 ;

    while( l <= r )
    {
        mid = (l+r)>>1 ;
        if(compressionTime[mid] >= x)
        {
            best = mid ;
            r = mid - 1 ;
        }
        else l = mid + 1 ;
    }
    return best ;
}
int menorIgual(int x)
{
    int l = 0 , r = sz(compressionTime)-1 , mid , best = -1 ;

    while(l <= r)
    {
        mid = (l+r)>>1 ;
        if(compressionTime[mid] <= x )
        {
            best = mid ;
            l = mid + 1 ;
        }
        else r = mid - 1 ;
    }

    return best ;
}

void coloca(set<int>::iterator l , set<int>::iterator r , int t )
{

    int xl = compressionX[*l] ;
    int xr = compressionX[*r] ;

    midRight[*l] = (xr - xl)>>1 ;
    midRight[*l] += xl ;
    midLeft[*r] = ( (xr-xl)%2 == 0 ) ? midRight[*l] : ( midRight[*l]+1);

    timeRight[*l] = t ;
    timeLeft[*r] = t ;

}

void apaga( set<int>::iterator l , set<int>::iterator r , int t )
{

    int xl = compressionX[*l] ;
    int xr = compressionX[*r] ;

    if(timeRight[*l] <= t )
        sweep.pb( Event( midRight[*l] , xl , 0 , timeRight[*l] , t ) ) ;

    if(timeLeft[*r] <= t)
        sweep.pb( Event( midLeft[*r] , xr , -1, timeLeft[*r] , t ) ) ;

}


int main()
{

    scanf("%d%d%d", &N , &K , &Q ) ;

    for(int i = 1 , x , t , a , b ; i <= N ; i++ )
    {
        scanf("%d%d%d%d", &x, &t, &a, &b ) ;
        myStores[t].pb( mkt(x,a,b) ) ;
        compressionX.pb(x) ;
    }

    compressionX.pb(-MAXT) ;
    compressionX.pb(MAXT);
    sort(all(compressionX));
    compressionX.erase( unique( all(compressionX) ) , compressionX.end() ) ;

    for(int i = 1 ; i <= K ; i++ )
    {

        sort(all(myStores[i])) ;

        for(auto &tup : myStores[i])
        {
            int l = 0 , r = sz(compressionX) - 1 , mid ;

            while(l <= r)
            {
                mid = (l+r)>>1 ;

                if( compressionX[mid] == get<0>(tup) ) break ;
                else if( compressionX[mid] < get<0>(tup) ) l =mid+1 ;
                else r = mid - 1 ;
            }

            get<0>(tup) = mid ;
            coordX[mid].pb( mk(get<1>(tup) , get<2>(tup)) ) ;
        }

       for(int j = 0 ; j < sz(myStores[i]) ; j++ )
        {

            int X = get<0>(myStores[i][j]) ;

            if(j != 0 && X == get<0>(myStores[i][j-1]) ) continue ;

            int mnTime =  coordX[ X ][0].ff ;
            int mxTime =  coordX[ X ][0].ss ;
            coordX[X].pb( mk(MAXT, MAXT) ) ;

            for(int g = 1 ; g < sz( coordX[ X ] ) ; g++ )
            {
                if( coordX[X][g].ff > mxTime )
                {
                    myVecOfPairs.pb( mk( mnTime , -X ) ) ;
                    myVecOfPairs.pb( mk( mxTime , X ) ) ;

                    mnTime = coordX[X][g].ff ;
                    mxTime = coordX[X][g].ss ;
                }
                else if(coordX[X][g].ss > mxTime ) mxTime = coordX[X][g].ss ;
            }

            coordX[X].clear() ;

        }

         

        sort(all(myVecOfPairs)) ;

        lojinhas.insert(0) ;
        lojinhas.insert( sz(compressionX) - 1 ) ;

        coloca( lojinhas.begin() , prev( lojinhas.end() ) , 1 ) ;

        for(auto e : myVecOfPairs )
        {
            int t = e.ff ;
            int x = e.ss ;

            set<int>::iterator itMore , itLess;

            if(x < 0)
            {
                itMore = lojinhas.upper_bound(-x) ;
                itLess = itMore , itLess-- ;

                apaga(itLess, itMore, t-1) ;

                lojinhas.insert(-x) ;

                itMore = lojinhas.find(-x) ;
                itLess = itMore , itLess-- ;

                coloca(itLess, itMore , t) ;

                itLess = itMore , itLess++ ;
                swap(itLess, itMore) ;

                coloca(itLess, itMore, t) ;

            }
            else
            {
                itMore = lojinhas.find(x) ;
                itLess = itMore , itLess-- ;

                apaga(itLess, itMore , t ) ;


                itLess = itMore , itLess++ ;
                swap(itLess, itMore ) ;

                apaga(itLess, itMore, t ) ;

                lojinhas.erase(itLess) ;

                itMore = lojinhas.upper_bound(x) ;
                itLess = itMore , itLess-- ;

                coloca(itLess, itMore, t+1 ) ;

            }

        }

        apaga( lojinhas.begin() , prev(lojinhas.end() ) , MAXT ) ;

        myVecOfPairs.clear() ;
        lojinhas.clear() ;

    }

    

    for(int i = 1 , l , y ; i <= Q ; i++ )
    {
        scanf("%d%d", &l, &y ) ;
        sweep.pb( Event(l,l,i,y,y) );
        compressionTime.pb(y) ;
    }

     
    sort(all(compressionTime)) ;
    compressionTime.erase( unique(all(compressionTime)) , compressionTime.end() );
     

    sort(all(sweep), [&](Event a, Event b)
         {
             if( a.xConta != b.xConta ) return a.xConta < b.xConta ;
             else return a.type < b.type ;
         } );

    for(auto &e : sweep ) e.t1 = maiorIgual(e.t1) , e.t2 = menorIgual(e.t2) ;
    

    seg.n = sz(compressionTime) ;

    for(auto e : sweep )
        if( e.type != 0 && e.t1 <= e.t2 )
            seg.insertEvent( e.t1, e.t2+1 , e ) ;

    seg.solve( 0 ) ;

    sort(all(sweep), [&](Event a, Event b)
     {
         if( a.xConta != b.xConta ) return a.xConta > b.xConta ;
         else return a.type < b.type ;
     } );

    for(int i = 1 ; i < 2*seg.n ; i++ ) seg.tree[i].clear() ;

    for(auto e : sweep )
        if(e.type != -1 && e.t1 <= e.t2 )
            seg.insertEvent( e.t1, e.t2+1, e ) ;

    seg.solve( -1 ) ;

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

}

 


#undef lp
#undef sz
#undef all
#undef lp
#undef pb
#undef sz
#undef all
#undef debug
#undef tiii
#undef mkt
#undef pii
#undef mk
#undef ll
#undef ff
#undef ss

inline void FASTIO::ignore() {
  if(REMAINING_CHARACTER == true) REMAINING_CHARACTER = false; else READ_CHARACTER = getchar();
}

inline void FASTIO::flush() {
  fflush(stdout);
}

// cin modifications

template <typename T>
inline bool FASTIO::READ_INT(T &x) {
  x = 0; T sig = 1;
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while (!isdigit(READ_CHARACTER) && READ_CHARACTER != EOF) sig = (READ_CHARACTER == '-' ? -sig : sig), READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while (isdigit(READ_CHARACTER)) x = x * 10 + READ_CHARACTER - '0', READ_CHARACTER = getchar();
  x *= sig; REMAINING_CHARACTER = true;
  return true;
}

template <typename T>
inline bool FASTIO::READ_STRING(T &x) {
  x = "";
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while ((READ_CHARACTER != '\n' && READ_CHARACTER != '\t' && READ_CHARACTER != ' ' && READ_CHARACTER != EOF)) x += READ_CHARACTER, READ_CHARACTER = getchar();
  REMAINING_CHARACTER = true;
  return true;
}

inline bool FASTIO::READ_GETLINE(std::string &x) {
  x = "";
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while ((READ_CHARACTER != '\n' && READ_CHARACTER != EOF)) x += READ_CHARACTER, READ_CHARACTER = getchar();
  REMAINING_CHARACTER = false;
  return true;
}

template <typename T>
inline bool FASTIO::READ_CHAR(T &x) {
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  x = READ_CHARACTER; REMAINING_CHARACTER = false;
  return true;
}


template<size_t N>
inline bool FASTIO::READ_CHAR_ARRAY(char (&x)[N]) {
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  char *ptr = &x[0];
  while ((READ_CHARACTER != '\n' && READ_CHARACTER != '\t' && READ_CHARACTER != ' ' && READ_CHARACTER != EOF)) *ptr++ = READ_CHARACTER, READ_CHARACTER = getchar();
  *ptr = '\0', REMAINING_CHARACTER = true;
  return true;
}

inline bool FASTIO::READ_CHAR_ARRAY(char*& x) {
  std::string y;
  if(READ_STRING(y) == false)
    return false;
  x = new char[(int)y.size() + 1];
  strcpy(x, y.c_str());
  return true;
}

template <typename T>
inline bool FASTIO::READ_FLOAT(T &x) {
  return (scanf("%f", &x) != EOF);
}

template <typename T>
inline bool FASTIO::READ_DOUBLE(T &x) {
  double y;
  if(scanf("%lf", &y) == EOF) return false;
  x = y;
  return true;
}

template<std::size_t N>
inline bool FASTIO::READ_BITSET(std::bitset<N> &x) {
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  int i = 0; REMAINING_CHARACTER = true;
  while (READ_CHARACTER == '0' || READ_CHARACTER == '1') x[i++] = READ_CHARACTER - '0', READ_CHARACTER = getchar();
  return true;
}

inline bool FASTIO::READ_VAR(short int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(long int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(long long int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned short int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned long &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned long long &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(std::string &x) {
  return READ_STRING(x);    
}

inline bool FASTIO::READ_VAR(char &x) {
  return READ_CHAR(x);
}

template<size_t N>
inline bool FASTIO::READ_VAR(char (&x)[N]) {
  return READ_CHAR_ARRAY(x);
}

inline bool FASTIO::READ_VAR(char*& x) {
  return READ_CHAR_ARRAY(x);
}

inline bool FASTIO::READ_VAR(float &x) {
  return READ_FLOAT(x);
}

inline bool FASTIO::READ_VAR(double &x) {
  return READ_DOUBLE(x);
}

inline bool FASTIO::READ_VAR(long double &x) {
  return READ_DOUBLE(x);
}

template<std::size_t N>
inline bool FASTIO::READ_VAR(std::bitset<N> &x) {
  return READ_BITSET(x);
}

// cout modifications

template <typename T>
inline void FASTIO::WRITE_INT(T x) {
  if (x < 0) {putchar('-'); x = -x; }
  char writeBuffer[20], *writePtr = writeBuffer;
  do {
    *writePtr++ = '0' + x % 10;
    x /= 10;
  }
  while (x);
  do  { putchar(*--writePtr); }
  while (writePtr > writeBuffer);
}

inline void FASTIO::WRITE_CHAR(char x) {
  putchar(x);
}

inline void FASTIO::WRITE_CHAR_ARRAY(const char *x) {
  while(*x != '\0')
    putchar(*x++);
}

inline void FASTIO::WRITE_STRING(std::string &x) {
  for(char c: x) 
    putchar(c);
}

inline void FASTIO::WRITE_FLOAT(float x) {
  printf("%f", x);
}

template <typename T>
inline void FASTIO::WRITE_DOUBLE(T x) {
  printf("%lf", (double)x);
}

template<std::size_t N>
inline void FASTIO::WRITE_BITSET(std::bitset<N> &x) {
  for(int i = (int)x.size() - 1; i >= 0; i--)
    putchar(x[i] + 48);
}

inline void FASTIO::WRITE_VAR(bool x) {
  WRITE_INT(x);
}

inline void FASTIO::WRITE_VAR(short int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(long int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(long long int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned short int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned long x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned long long x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(std::string &x) {
  WRITE_STRING(x);    
}

inline void FASTIO::WRITE_VAR(char x) {
  WRITE_CHAR(x);
}

inline void FASTIO::WRITE_VAR(const char *x) {
  WRITE_CHAR_ARRAY(x);
}

inline void FASTIO::WRITE_VAR(float x) {
  WRITE_FLOAT(x);
}

inline void FASTIO::WRITE_VAR(double x) {
  WRITE_DOUBLE(x);
}

inline void FASTIO::WRITE_VAR(long double x) {
  WRITE_DOUBLE(x);
}

template<std::size_t N>
inline void FASTIO::WRITE_VAR(std::bitset<N> &x) {
  WRITE_BITSET(x);
}  

Compilation message (stderr)

new_home.cpp:37: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   37 | #pragma GCC optimization ("O3")
      | 
new_home.cpp:38: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   38 | #pragma GCC optimization ("unroll-loops")
      | 
new_home.cpp: In instantiation of 'void FASTIO::WRITE_INT(T) [with T = bool]':
new_home.cpp:605:14:   required from here
new_home.cpp:564:9: warning: comparison of constant '0' with boolean expression is always false [-Wbool-compare]
  564 |   if (x < 0) {putchar('-'); x = -x; }
      |       ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:201:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  201 |     scanf("%d%d%d", &N , &K , &Q ) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:205:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  205 |         scanf("%d%d%d%d", &x, &t, &a, &b ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:336:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  336 |         scanf("%d%d", &l, &y ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~
new_home.cpp:222:52: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
  222 |             int l = 0 , r = sz(compressionX) - 1 , mid ;
      |                                                    ^~~

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