Submission #295268

#	Time	Username	Problem	Language	Result	Execution time	Memory
295268		CaroLinda	New Home (APIO18_new_home)	C++14	80 / 100	5135 ms	778512 KiB

new_home

#include <bits/stdc++.h>
 
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,fma,tune=native")
#pragma GCC optimize("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+100 ;
const int MAXT = 1e9+10 ;
const int MAX_COORD = 3e8+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++ )
        {
        	//debug("Em %d:\n" , i ) ;
            int mxNegative = -MAXT , mnPositive = MAXT ;
 
            for(auto e : tree[i])
            {
                if( e.type == forbiddenType ) continue ;

                //debug("coord %d %d, e tempo %d %d e tipo %d\n" , e.xConta, e.xIntercept, e.t1, e.t2, e.type ) ;

                if( e.type > 0 )
                {
                    ansQuery[ e.type ] = max( ansQuery[e.type] , (forbiddenType == 0) ? mxNegative - e.xConta : e.xConta-mnPositive ) ;
                }
                else
                {
                    if(forbiddenType == 0) mxNegative = max(mxNegative, e.xIntercept ) ;
                    else mnPositive = min(mnPositive, e.xIntercept ) ;
                }
            }
        }
    }
 
} seg ;
 
//O ANO PODE IR ATÉ 10^8
//VAI TER QUE FAZER COMPRESSÃO
 
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 mxTime = max(mxTime, coordX[X][g].ss ) ;
            }
 
            coordX[X].clear() ;
 
        }
 
        //Cada x eh unico e ta comprimido, pode ser o id dele
 
        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(auto e : sweep ) debug("[%d,%d] %d time[%d,%d]\n", e.xConta, e.xIntercept, e.type , e.t1, e.t2 ) ;
 
    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) ;
    }
 
    //Indeed, compression time!
    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) ;
   	//for(auto e : sweep ) printf("coord %d %d, e tempo %d %d e tipo %d\n" , e.xConta, e.xIntercept, e.t1, e.t2, e.type ) ;
 
    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] ) ;
 
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:172:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  172 |     scanf("%d%d%d", &N , &K , &Q ) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:176:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  176 |         scanf("%d%d%d%d", &x, &t, &a, &b ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:307:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  307 |         scanf("%d%d", &l, &y ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~
new_home.cpp:193:52: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
  193 |             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