oj.uz

Submission #295014

# Submission time Handle Problem Language Result Execution time Memory
295014 2020-09-09T12:18:15 Z CaroLinda New Home (APIO18_new_home) C++14
57 / 100
 5000 ms 784908 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 = 1e6+10 ;
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< tiii > myVecOfTuples ;
set<int> store[MAXN] ;
map< pii , int > segments[MAXN] ;
vector<Event> sweep ;
map<int,int> compressionTime ;
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)
    {
        Event a = Event( midPointL, *itLess, 0 , segments[type][ mk(midPointL,*itLess) ] , clock );
        Event b = Event( midPointR, *itMore, -1 , segments[type][ mk(midPointR, *itMore) ] , clock ) ;

        segments[type].erase( segments[type].find( mk(midPointL, *itLess) ) ) ;
        segments[type].erase( segments[type].find( mk(midPointR, *itMore) ) ) ;

        if(a.t1 <= a.t2)
            sweep.pb(a);
        if(b.t1 <= b.t2 )
            sweep.pb(b) ;
    }
    else
    {
        segments[ type ][ mk(midPointL, *itLess) ] = clock ;
        segments[type][ 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 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) );
    }

    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 )
    {
        if( compressionTime.find( e.t1 ) == compressionTime.end() )
            compressionTime[e.t1] = 0 ;

        if( compressionTime.find( e.t2 ) == compressionTime.end() )
            compressionTime[e.t2] = 0 ;

    }
    int Key = 0 ;
    for(auto &e : compressionTime ) e.ss = Key++ ;

    seg.n = sz(compressionTime) ;

    for(auto e : sweep )
    {
        if(e.type == 0) continue ;
        seg.insertEvent( compressionTime[e.t1] , compressionTime[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) continue ;
        seg.insertEvent( compressionTime[e.t1] , compressionTime[e.t2]+1 , e ) ;
    }

    seg.solve( -1 ) ;


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

}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 188152 KB Output is correct
2 Correct 127 ms 188376 KB Output is correct
3 Correct 126 ms 188152 KB Output is correct
4 Correct 126 ms 188152 KB Output is correct
5 Correct 127 ms 188280 KB Output is correct
6 Correct 131 ms 188792 KB Output is correct
7 Correct 132 ms 188920 KB Output is correct
8 Correct 134 ms 188920 KB Output is correct
9 Correct 129 ms 188924 KB Output is correct
10 Correct 132 ms 188920 KB Output is correct
11 Correct 135 ms 188664 KB Output is correct
12 Correct 132 ms 188664 KB Output is correct
13 Correct 132 ms 188664 KB Output is correct
14 Correct 130 ms 188596 KB Output is correct
15 Correct 129 ms 188792 KB Output is correct
16 Correct 129 ms 188920 KB Output is correct
17 Correct 131 ms 188792 KB Output is correct
18 Correct 132 ms 188792 KB Output is correct
19 Correct 131 ms 188920 KB Output is correct
20 Correct 129 ms 188792 KB Output is correct
21 Correct 128 ms 188536 KB Output is correct
22 Correct 134 ms 189048 KB Output is correct
23 Correct 131 ms 188920 KB Output is correct
24 Correct 132 ms 188916 KB Output is correct
25 Correct 130 ms 188804 KB Output is correct
26 Correct 133 ms 188664 KB Output is correct
27 Correct 132 ms 188412 KB Output is correct
28 Correct 133 ms 188664 KB Output is correct
29 Correct 129 ms 188792 KB Output is correct
30 Correct 129 ms 188536 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 188152 KB Output is correct
2 Correct 127 ms 188376 KB Output is correct
3 Correct 126 ms 188152 KB Output is correct
4 Correct 126 ms 188152 KB Output is correct
5 Correct 127 ms 188280 KB Output is correct
6 Correct 131 ms 188792 KB Output is correct
7 Correct 132 ms 188920 KB Output is correct
8 Correct 134 ms 188920 KB Output is correct
9 Correct 129 ms 188924 KB Output is correct
10 Correct 132 ms 188920 KB Output is correct
11 Correct 135 ms 188664 KB Output is correct
12 Correct 132 ms 188664 KB Output is correct
13 Correct 132 ms 188664 KB Output is correct
14 Correct 130 ms 188596 KB Output is correct
15 Correct 129 ms 188792 KB Output is correct
16 Correct 129 ms 188920 KB Output is correct
17 Correct 131 ms 188792 KB Output is correct
18 Correct 132 ms 188792 KB Output is correct
19 Correct 131 ms 188920 KB Output is correct
20 Correct 129 ms 188792 KB Output is correct
21 Correct 128 ms 188536 KB Output is correct
22 Correct 134 ms 189048 KB Output is correct
23 Correct 131 ms 188920 KB Output is correct
24 Correct 132 ms 188916 KB Output is correct
25 Correct 130 ms 188804 KB Output is correct
26 Correct 133 ms 188664 KB Output is correct
27 Correct 132 ms 188412 KB Output is correct
28 Correct 133 ms 188664 KB Output is correct
29 Correct 129 ms 188792 KB Output is correct
30 Correct 129 ms 188536 KB Output is correct
31 Correct 2643 ms 317608 KB Output is correct
32 Correct 199 ms 197232 KB Output is correct
33 Correct 2274 ms 308792 KB Output is correct
34 Correct 2601 ms 309432 KB Output is correct
35 Correct 2770 ms 317148 KB Output is correct
36 Correct 2565 ms 316716 KB Output is correct
37 Correct 1701 ms 300624 KB Output is correct
38 Correct 1638 ms 300492 KB Output is correct
39 Correct 1182 ms 288084 KB Output is correct
40 Correct 1222 ms 291252 KB Output is correct
41 Correct 2349 ms 296396 KB Output is correct
42 Correct 2328 ms 297368 KB Output is correct
43 Correct 197 ms 194876 KB Output is correct
44 Correct 2343 ms 295816 KB Output is correct
45 Correct 2243 ms 287548 KB Output is correct
46 Correct 2000 ms 272208 KB Output is correct
47 Correct 941 ms 270988 KB Output is correct
48 Correct 901 ms 266200 KB Output is correct
49 Correct 1027 ms 277068 KB Output is correct
50 Correct 1187 ms 294604 KB Output is correct
51 Correct 1071 ms 271824 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3927 ms 596096 KB Output is correct
2 Correct 4283 ms 551468 KB Output is correct
3 Correct 4256 ms 784908 KB Output is correct
4 Correct 3976 ms 619568 KB Output is correct
5 Correct 4474 ms 554552 KB Output is correct
6 Correct 4274 ms 551500 KB Output is correct
7 Correct 4104 ms 771800 KB Output is correct
8 Correct 3728 ms 616960 KB Output is correct
9 Correct 3648 ms 563912 KB Output is correct
10 Correct 3735 ms 552184 KB Output is correct
11 Correct 2457 ms 553736 KB Output is correct
12 Correct 2478 ms 552628 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5132 ms 467376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 188152 KB Output is correct
2 Correct 127 ms 188376 KB Output is correct
3 Correct 126 ms 188152 KB Output is correct
4 Correct 126 ms 188152 KB Output is correct
5 Correct 127 ms 188280 KB Output is correct
6 Correct 131 ms 188792 KB Output is correct
7 Correct 132 ms 188920 KB Output is correct
8 Correct 134 ms 188920 KB Output is correct
9 Correct 129 ms 188924 KB Output is correct
10 Correct 132 ms 188920 KB Output is correct
11 Correct 135 ms 188664 KB Output is correct
12 Correct 132 ms 188664 KB Output is correct
13 Correct 132 ms 188664 KB Output is correct
14 Correct 130 ms 188596 KB Output is correct
15 Correct 129 ms 188792 KB Output is correct
16 Correct 129 ms 188920 KB Output is correct
17 Correct 131 ms 188792 KB Output is correct
18 Correct 132 ms 188792 KB Output is correct
19 Correct 131 ms 188920 KB Output is correct
20 Correct 129 ms 188792 KB Output is correct
21 Correct 128 ms 188536 KB Output is correct
22 Correct 134 ms 189048 KB Output is correct
23 Correct 131 ms 188920 KB Output is correct
24 Correct 132 ms 188916 KB Output is correct
25 Correct 130 ms 188804 KB Output is correct
26 Correct 133 ms 188664 KB Output is correct
27 Correct 132 ms 188412 KB Output is correct
28 Correct 133 ms 188664 KB Output is correct
29 Correct 129 ms 188792 KB Output is correct
30 Correct 129 ms 188536 KB Output is correct
31 Correct 2643 ms 317608 KB Output is correct
32 Correct 199 ms 197232 KB Output is correct
33 Correct 2274 ms 308792 KB Output is correct
34 Correct 2601 ms 309432 KB Output is correct
35 Correct 2770 ms 317148 KB Output is correct
36 Correct 2565 ms 316716 KB Output is correct
37 Correct 1701 ms 300624 KB Output is correct
38 Correct 1638 ms 300492 KB Output is correct
39 Correct 1182 ms 288084 KB Output is correct
40 Correct 1222 ms 291252 KB Output is correct
41 Correct 2349 ms 296396 KB Output is correct
42 Correct 2328 ms 297368 KB Output is correct
43 Correct 197 ms 194876 KB Output is correct
44 Correct 2343 ms 295816 KB Output is correct
45 Correct 2243 ms 287548 KB Output is correct
46 Correct 2000 ms 272208 KB Output is correct
47 Correct 941 ms 270988 KB Output is correct
48 Correct 901 ms 266200 KB Output is correct
49 Correct 1027 ms 277068 KB Output is correct
50 Correct 1187 ms 294604 KB Output is correct
51 Correct 1071 ms 271824 KB Output is correct
52 Correct 2655 ms 357420 KB Output is correct
53 Correct 2714 ms 343244 KB Output is correct
54 Correct 2777 ms 331476 KB Output is correct
55 Correct 2286 ms 316912 KB Output is correct
56 Correct 2359 ms 325460 KB Output is correct
57 Correct 2237 ms 301396 KB Output is correct
58 Correct 2414 ms 315672 KB Output is correct
59 Correct 2559 ms 323504 KB Output is correct
60 Correct 2344 ms 302964 KB Output is correct
61 Correct 355 ms 231268 KB Output is correct
62 Correct 2586 ms 356664 KB Output is correct
63 Correct 2656 ms 337488 KB Output is correct
64 Correct 2622 ms 331212 KB Output is correct
65 Correct 2504 ms 316404 KB Output is correct
66 Correct 2301 ms 301416 KB Output is correct
67 Correct 437 ms 227724 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 188152 KB Output is correct
2 Correct 127 ms 188376 KB Output is correct
3 Correct 126 ms 188152 KB Output is correct
4 Correct 126 ms 188152 KB Output is correct
5 Correct 127 ms 188280 KB Output is correct
6 Correct 131 ms 188792 KB Output is correct
7 Correct 132 ms 188920 KB Output is correct
8 Correct 134 ms 188920 KB Output is correct
9 Correct 129 ms 188924 KB Output is correct
10 Correct 132 ms 188920 KB Output is correct
11 Correct 135 ms 188664 KB Output is correct
12 Correct 132 ms 188664 KB Output is correct
13 Correct 132 ms 188664 KB Output is correct
14 Correct 130 ms 188596 KB Output is correct
15 Correct 129 ms 188792 KB Output is correct
16 Correct 129 ms 188920 KB Output is correct
17 Correct 131 ms 188792 KB Output is correct
18 Correct 132 ms 188792 KB Output is correct
19 Correct 131 ms 188920 KB Output is correct
20 Correct 129 ms 188792 KB Output is correct
21 Correct 128 ms 188536 KB Output is correct
22 Correct 134 ms 189048 KB Output is correct
23 Correct 131 ms 188920 KB Output is correct
24 Correct 132 ms 188916 KB Output is correct
25 Correct 130 ms 188804 KB Output is correct
26 Correct 133 ms 188664 KB Output is correct
27 Correct 132 ms 188412 KB Output is correct
28 Correct 133 ms 188664 KB Output is correct
29 Correct 129 ms 188792 KB Output is correct
30 Correct 129 ms 188536 KB Output is correct
31 Correct 2643 ms 317608 KB Output is correct
32 Correct 199 ms 197232 KB Output is correct
33 Correct 2274 ms 308792 KB Output is correct
34 Correct 2601 ms 309432 KB Output is correct
35 Correct 2770 ms 317148 KB Output is correct
36 Correct 2565 ms 316716 KB Output is correct
37 Correct 1701 ms 300624 KB Output is correct
38 Correct 1638 ms 300492 KB Output is correct
39 Correct 1182 ms 288084 KB Output is correct
40 Correct 1222 ms 291252 KB Output is correct
41 Correct 2349 ms 296396 KB Output is correct
42 Correct 2328 ms 297368 KB Output is correct
43 Correct 197 ms 194876 KB Output is correct
44 Correct 2343 ms 295816 KB Output is correct
45 Correct 2243 ms 287548 KB Output is correct
46 Correct 2000 ms 272208 KB Output is correct
47 Correct 941 ms 270988 KB Output is correct
48 Correct 901 ms 266200 KB Output is correct
49 Correct 1027 ms 277068 KB Output is correct
50 Correct 1187 ms 294604 KB Output is correct
51 Correct 1071 ms 271824 KB Output is correct
52 Correct 3927 ms 596096 KB Output is correct
53 Correct 4283 ms 551468 KB Output is correct
54 Correct 4256 ms 784908 KB Output is correct
55 Correct 3976 ms 619568 KB Output is correct
56 Correct 4474 ms 554552 KB Output is correct
57 Correct 4274 ms 551500 KB Output is correct
58 Correct 4104 ms 771800 KB Output is correct
59 Correct 3728 ms 616960 KB Output is correct
60 Correct 3648 ms 563912 KB Output is correct
61 Correct 3735 ms 552184 KB Output is correct
62 Correct 2457 ms 553736 KB Output is correct
63 Correct 2478 ms 552628 KB Output is correct
64 Execution timed out 5132 ms 467376 KB Time limit exceeded
65 Halted 0 ms 0 KB -