oj.uz

Submission #295084

# Submission time Handle Problem Language Result Execution time Memory
295084 2020-09-09T13:13:03 Z CaroLinda New Home (APIO18_new_home) C++14
0 / 100
 4469 ms 654932 KB 
#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 = 1e8+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++ )
        {
            int mxNegative = -MAXT , mnPositive = MAXT ;

            for(auto e : tree[i])
            {
                if( e.type == forbiddenType ) continue ;
                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 ;
vector<int> compressionTime ;
set<int> store[MAXN] ;
vector< tiii > myVecOfTuples ;
map< pii , int > segments[MAXN] ;
vector<Event> sweep ;
map<int, vector<pii> > mySet[MAXN] ;

void operation( set<int>::iterator itLess, set<int>::iterator itMore , int type , int clock , bool isRemoval )
{
    int midPointL = (*itMore - *itLess)>>1 ;
    midPointL += *itLess ;

    int midPointR = midPointL ;

    if( (*itMore - (*itLess)) % 2 != 0 ) midPointR++;


    if(isRemoval)
    {
        auto itL = segments[type].find( mk(midPointL, *itLess) ) ;
        auto itM = segments[type].find( mk(midPointR, *itMore) ) ;

        Event a = Event( midPointL, *itLess, 0 , (itL == segments[type].end() ? clock+1 : itL->ss)  , clock );
        Event b = Event( midPointR, *itMore, -1 , (itM == segments[type].end() ? clock+1 : itM->ss) , clock ) ;

        segments[type].erase( itL ) ;
        segments[type].erase( itM ) ;

        if(a.t1 <= a.t2)
            sweep.pb(a);
        if(b.t1 <= b.t2 )
            sweep.pb(b) ;
    }
    else
    {
        segments[ type ].insert( mk(mk(midPointL, *itLess), clock) ) ;
        segments[type].insert( mk(mk(midPointR, *itMore),clock) ) ;
    }

}

void insertion(int x_coord, int type, int clock )
{

    auto itMore = store[type].lower_bound(x_coord) ;
    auto itLess = itMore ; itLess-- ;

    operation( itLess, itMore, type, clock-1 , true) ;

    store[type].insert( x_coord ) ;

    itMore = store[type].find( x_coord ) ;
    itLess = itMore ; itLess-- ;

    operation( itLess, itMore, type, clock, false ) ;

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

    operation( itLess, itMore, type, clock, false );

}

void removal(int x_coord, int type, int clock )
{

    auto itMore = store[type].find(x_coord) ;
    auto itLess = itMore ; itLess-- ;

    operation( itLess, itMore, type, clock, true ) ;

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

    operation( itLess, itMore, type, clock, true ) ;

    store[type].erase(itLess);

    itMore = store[type].lower_bound(x_coord);
    itLess = itMore ; itLess--;

    operation( itLess, itMore, type, clock+1, false ) ;

}

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 ;
}

int main()
{

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

        store[i].insert( -MAX_COORD ) ;
        store[i].insert( MAX_COORD ) ;

        operation( store[i].begin() , prev( store[i].end() ) , i , 1, false ) ;

    }
    for(int i = 1 , x , t , a , b ; i <= N ; i++ )
    {
        scanf("%d%d%d%d", &x, &t, &a, &b ) ;
        mySet[t][x].push_back( mk(a,b) ) ;
    }

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

        for(auto &aux: mySet[i] )
        {
            vector<pii> x_coord = aux.ss ;

            sort(all(x_coord)) ;
            x_coord.pb( mk( MAXT, MAXT ) ) ;

            int mnTime = x_coord[0].ff ;
            int mxTime = x_coord[0].ss ;

            for(int j = 1 ; j < sz(x_coord) ; j++ )
            {
                if( x_coord[j].ff > mxTime )
                {
                    myVecOfTuples.pb( mkt( mnTime , -i, aux.ff ) ) ;
                    myVecOfTuples.pb( mkt( mxTime, i, aux.ff ) ) ;

                    mnTime = x_coord[j].ff ;
                    mxTime = x_coord[j].ss ;
                }
                else mxTime = max(mxTime, x_coord[j].ss ) ;
            }

        }
    }

    sort(all(myVecOfTuples)) ;

    for(auto tup : myVecOfTuples )
    {

        int clock = get<0>(tup) ;
        int type = get<1>(tup) ;
        int x_coord = get<2>(tup) ;

        if( type < 0 ) insertion( x_coord , -type, clock ) ;
        else removal( x_coord, type, clock );

    }

    for(int i = 1 ; i <= K ; i++ )
        operation( store[i].begin() , prev( store[i].end() ) , i , MAXT, true ) ;

    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] > 100000010 ? -1 : ansQuery[i] ) ;

}

/*
2 1 1
39682063 1 1 100000000
29000832 1 1 100000000
34341447 100000000

2 1 1
39682063 1 1 100000000
29000832 1 1 100000000
34341447 100000000

5 4 1
39682063 3 1 100000000
37986244 2 1 100000000
29273266 1 1 100000000
33173370 4 1 100000000
29000832 3 1 100000000
34341447 100000000



5 2 2
4 2 3 3
5 1 2 5
5 1 2 5
5 1 5 5
4 1 3 3
90 3
7 10

1 1 1
5 1 1 10
7 5

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

6 3 4
10 1 1 100000000
13 2 1 100000000
10 2 1 100000000
1 3 1 100000000
15 1 1 100000000
26 3 1 100000000
15 20
30 100000000
50 800
100000000 1

4 2 4
3 1 1 10
4 1 8 10
9 2 2 4
7 2 5 7
5 3
5 6
5 9
1 10

1 1 1
100000000 1 1 1 1
1 1

*/

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:214:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  214 |     scanf("%d%d%d", &N , &K , &Q ) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:226:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  226 |         scanf("%d%d%d%d", &x, &t, &a, &b ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:278:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  278 |         scanf("%d%d", &l, &y ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 56704 KB Output is correct
2 Correct 38 ms 56716 KB Output is correct
3 Correct 39 ms 56704 KB Output is correct
4 Correct 38 ms 56696 KB Output is correct
5 Runtime error 110 ms 114936 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 56704 KB Output is correct
2 Correct 38 ms 56716 KB Output is correct
3 Correct 39 ms 56704 KB Output is correct
4 Correct 38 ms 56696 KB Output is correct
5 Runtime error 110 ms 114936 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2673 ms 438188 KB Output is correct
2 Correct 2928 ms 411180 KB Output is correct
3 Correct 2974 ms 654932 KB Output is correct
4 Correct 2730 ms 472372 KB Output is correct
5 Runtime error 1377 ms 305148 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4469 ms 526932 KB Output is correct
2 Runtime error 252 ms 123128 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 56704 KB Output is correct
2 Correct 38 ms 56716 KB Output is correct
3 Correct 39 ms 56704 KB Output is correct
4 Correct 38 ms 56696 KB Output is correct
5 Runtime error 110 ms 114936 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 56704 KB Output is correct
2 Correct 38 ms 56716 KB Output is correct
3 Correct 39 ms 56704 KB Output is correct
4 Correct 38 ms 56696 KB Output is correct
5 Runtime error 110 ms 114936 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -