oj.uz

Submission #295011

# Submission time Handle Problem Language Result Execution time Memory
295011 2020-09-09T12:14:10 Z CaroLinda New Home (APIO18_new_home) C++14
57 / 100
 4427 ms 714588 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 = 6e5+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< 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*MAXN ; 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 78 ms 113016 KB Output is correct
2 Correct 78 ms 113016 KB Output is correct
3 Correct 79 ms 113016 KB Output is correct
4 Correct 78 ms 113144 KB Output is correct
5 Correct 79 ms 113188 KB Output is correct
6 Correct 83 ms 113656 KB Output is correct
7 Correct 82 ms 113912 KB Output is correct
8 Correct 84 ms 113784 KB Output is correct
9 Correct 87 ms 113912 KB Output is correct
10 Correct 82 ms 113656 KB Output is correct
11 Correct 82 ms 113656 KB Output is correct
12 Correct 83 ms 113528 KB Output is correct
13 Correct 84 ms 113528 KB Output is correct
14 Correct 85 ms 113528 KB Output is correct
15 Correct 86 ms 113656 KB Output is correct
16 Correct 84 ms 113784 KB Output is correct
17 Correct 81 ms 113656 KB Output is correct
18 Correct 82 ms 113656 KB Output is correct
19 Correct 84 ms 113784 KB Output is correct
20 Correct 83 ms 113656 KB Output is correct
21 Correct 79 ms 113400 KB Output is correct
22 Correct 84 ms 113912 KB Output is correct
23 Correct 84 ms 113784 KB Output is correct
24 Correct 83 ms 113784 KB Output is correct
25 Correct 84 ms 113688 KB Output is correct
26 Correct 82 ms 113528 KB Output is correct
27 Correct 80 ms 113404 KB Output is correct
28 Correct 84 ms 113656 KB Output is correct
29 Correct 81 ms 113552 KB Output is correct
30 Correct 82 ms 113400 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 113016 KB Output is correct
2 Correct 78 ms 113016 KB Output is correct
3 Correct 79 ms 113016 KB Output is correct
4 Correct 78 ms 113144 KB Output is correct
5 Correct 79 ms 113188 KB Output is correct
6 Correct 83 ms 113656 KB Output is correct
7 Correct 82 ms 113912 KB Output is correct
8 Correct 84 ms 113784 KB Output is correct
9 Correct 87 ms 113912 KB Output is correct
10 Correct 82 ms 113656 KB Output is correct
11 Correct 82 ms 113656 KB Output is correct
12 Correct 83 ms 113528 KB Output is correct
13 Correct 84 ms 113528 KB Output is correct
14 Correct 85 ms 113528 KB Output is correct
15 Correct 86 ms 113656 KB Output is correct
16 Correct 84 ms 113784 KB Output is correct
17 Correct 81 ms 113656 KB Output is correct
18 Correct 82 ms 113656 KB Output is correct
19 Correct 84 ms 113784 KB Output is correct
20 Correct 83 ms 113656 KB Output is correct
21 Correct 79 ms 113400 KB Output is correct
22 Correct 84 ms 113912 KB Output is correct
23 Correct 84 ms 113784 KB Output is correct
24 Correct 83 ms 113784 KB Output is correct
25 Correct 84 ms 113688 KB Output is correct
26 Correct 82 ms 113528 KB Output is correct
27 Correct 80 ms 113404 KB Output is correct
28 Correct 84 ms 113656 KB Output is correct
29 Correct 81 ms 113552 KB Output is correct
30 Correct 82 ms 113400 KB Output is correct
31 Correct 2623 ms 245432 KB Output is correct
32 Correct 153 ms 122992 KB Output is correct
33 Correct 2270 ms 235876 KB Output is correct
34 Correct 2602 ms 236512 KB Output is correct
35 Correct 2693 ms 244188 KB Output is correct
36 Correct 2441 ms 244076 KB Output is correct
37 Correct 1613 ms 227788 KB Output is correct
38 Correct 1558 ms 227524 KB Output is correct
39 Correct 1127 ms 215116 KB Output is correct
40 Correct 1165 ms 218576 KB Output is correct
41 Correct 2213 ms 224212 KB Output is correct
42 Correct 2195 ms 225104 KB Output is correct
43 Correct 155 ms 122048 KB Output is correct
44 Correct 2170 ms 223308 KB Output is correct
45 Correct 2139 ms 215228 KB Output is correct
46 Correct 1908 ms 199840 KB Output is correct
47 Correct 887 ms 198608 KB Output is correct
48 Correct 844 ms 193620 KB Output is correct
49 Correct 981 ms 204752 KB Output is correct
50 Correct 1122 ms 222288 KB Output is correct
51 Correct 1014 ms 199528 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3835 ms 525112 KB Output is correct
2 Correct 4165 ms 482316 KB Output is correct
3 Correct 4152 ms 714588 KB Output is correct
4 Correct 3936 ms 548132 KB Output is correct
5 Correct 4427 ms 483396 KB Output is correct
6 Correct 4259 ms 489284 KB Output is correct
7 Correct 4056 ms 710984 KB Output is correct
8 Correct 3663 ms 555736 KB Output is correct
9 Correct 3692 ms 502428 KB Output is correct
10 Correct 3570 ms 490156 KB Output is correct
11 Correct 2421 ms 491036 KB Output is correct
12 Correct 2404 ms 490468 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 3905 ms 501632 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 113016 KB Output is correct
2 Correct 78 ms 113016 KB Output is correct
3 Correct 79 ms 113016 KB Output is correct
4 Correct 78 ms 113144 KB Output is correct
5 Correct 79 ms 113188 KB Output is correct
6 Correct 83 ms 113656 KB Output is correct
7 Correct 82 ms 113912 KB Output is correct
8 Correct 84 ms 113784 KB Output is correct
9 Correct 87 ms 113912 KB Output is correct
10 Correct 82 ms 113656 KB Output is correct
11 Correct 82 ms 113656 KB Output is correct
12 Correct 83 ms 113528 KB Output is correct
13 Correct 84 ms 113528 KB Output is correct
14 Correct 85 ms 113528 KB Output is correct
15 Correct 86 ms 113656 KB Output is correct
16 Correct 84 ms 113784 KB Output is correct
17 Correct 81 ms 113656 KB Output is correct
18 Correct 82 ms 113656 KB Output is correct
19 Correct 84 ms 113784 KB Output is correct
20 Correct 83 ms 113656 KB Output is correct
21 Correct 79 ms 113400 KB Output is correct
22 Correct 84 ms 113912 KB Output is correct
23 Correct 84 ms 113784 KB Output is correct
24 Correct 83 ms 113784 KB Output is correct
25 Correct 84 ms 113688 KB Output is correct
26 Correct 82 ms 113528 KB Output is correct
27 Correct 80 ms 113404 KB Output is correct
28 Correct 84 ms 113656 KB Output is correct
29 Correct 81 ms 113552 KB Output is correct
30 Correct 82 ms 113400 KB Output is correct
31 Correct 2623 ms 245432 KB Output is correct
32 Correct 153 ms 122992 KB Output is correct
33 Correct 2270 ms 235876 KB Output is correct
34 Correct 2602 ms 236512 KB Output is correct
35 Correct 2693 ms 244188 KB Output is correct
36 Correct 2441 ms 244076 KB Output is correct
37 Correct 1613 ms 227788 KB Output is correct
38 Correct 1558 ms 227524 KB Output is correct
39 Correct 1127 ms 215116 KB Output is correct
40 Correct 1165 ms 218576 KB Output is correct
41 Correct 2213 ms 224212 KB Output is correct
42 Correct 2195 ms 225104 KB Output is correct
43 Correct 155 ms 122048 KB Output is correct
44 Correct 2170 ms 223308 KB Output is correct
45 Correct 2139 ms 215228 KB Output is correct
46 Correct 1908 ms 199840 KB Output is correct
47 Correct 887 ms 198608 KB Output is correct
48 Correct 844 ms 193620 KB Output is correct
49 Correct 981 ms 204752 KB Output is correct
50 Correct 1122 ms 222288 KB Output is correct
51 Correct 1014 ms 199528 KB Output is correct
52 Correct 2608 ms 284348 KB Output is correct
53 Correct 2655 ms 270204 KB Output is correct
54 Correct 2690 ms 258452 KB Output is correct
55 Correct 2303 ms 243600 KB Output is correct
56 Correct 2317 ms 252260 KB Output is correct
57 Correct 2260 ms 228300 KB Output is correct
58 Correct 2360 ms 242520 KB Output is correct
59 Correct 2438 ms 250136 KB Output is correct
60 Correct 2335 ms 229456 KB Output is correct
61 Correct 316 ms 157916 KB Output is correct
62 Correct 2565 ms 283384 KB Output is correct
63 Correct 2656 ms 264144 KB Output is correct
64 Correct 2607 ms 257748 KB Output is correct
65 Correct 2481 ms 243148 KB Output is correct
66 Correct 2303 ms 227792 KB Output is correct
67 Correct 387 ms 153684 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 113016 KB Output is correct
2 Correct 78 ms 113016 KB Output is correct
3 Correct 79 ms 113016 KB Output is correct
4 Correct 78 ms 113144 KB Output is correct
5 Correct 79 ms 113188 KB Output is correct
6 Correct 83 ms 113656 KB Output is correct
7 Correct 82 ms 113912 KB Output is correct
8 Correct 84 ms 113784 KB Output is correct
9 Correct 87 ms 113912 KB Output is correct
10 Correct 82 ms 113656 KB Output is correct
11 Correct 82 ms 113656 KB Output is correct
12 Correct 83 ms 113528 KB Output is correct
13 Correct 84 ms 113528 KB Output is correct
14 Correct 85 ms 113528 KB Output is correct
15 Correct 86 ms 113656 KB Output is correct
16 Correct 84 ms 113784 KB Output is correct
17 Correct 81 ms 113656 KB Output is correct
18 Correct 82 ms 113656 KB Output is correct
19 Correct 84 ms 113784 KB Output is correct
20 Correct 83 ms 113656 KB Output is correct
21 Correct 79 ms 113400 KB Output is correct
22 Correct 84 ms 113912 KB Output is correct
23 Correct 84 ms 113784 KB Output is correct
24 Correct 83 ms 113784 KB Output is correct
25 Correct 84 ms 113688 KB Output is correct
26 Correct 82 ms 113528 KB Output is correct
27 Correct 80 ms 113404 KB Output is correct
28 Correct 84 ms 113656 KB Output is correct
29 Correct 81 ms 113552 KB Output is correct
30 Correct 82 ms 113400 KB Output is correct
31 Correct 2623 ms 245432 KB Output is correct
32 Correct 153 ms 122992 KB Output is correct
33 Correct 2270 ms 235876 KB Output is correct
34 Correct 2602 ms 236512 KB Output is correct
35 Correct 2693 ms 244188 KB Output is correct
36 Correct 2441 ms 244076 KB Output is correct
37 Correct 1613 ms 227788 KB Output is correct
38 Correct 1558 ms 227524 KB Output is correct
39 Correct 1127 ms 215116 KB Output is correct
40 Correct 1165 ms 218576 KB Output is correct
41 Correct 2213 ms 224212 KB Output is correct
42 Correct 2195 ms 225104 KB Output is correct
43 Correct 155 ms 122048 KB Output is correct
44 Correct 2170 ms 223308 KB Output is correct
45 Correct 2139 ms 215228 KB Output is correct
46 Correct 1908 ms 199840 KB Output is correct
47 Correct 887 ms 198608 KB Output is correct
48 Correct 844 ms 193620 KB Output is correct
49 Correct 981 ms 204752 KB Output is correct
50 Correct 1122 ms 222288 KB Output is correct
51 Correct 1014 ms 199528 KB Output is correct
52 Correct 3835 ms 525112 KB Output is correct
53 Correct 4165 ms 482316 KB Output is correct
54 Correct 4152 ms 714588 KB Output is correct
55 Correct 3936 ms 548132 KB Output is correct
56 Correct 4427 ms 483396 KB Output is correct
57 Correct 4259 ms 489284 KB Output is correct
58 Correct 4056 ms 710984 KB Output is correct
59 Correct 3663 ms 555736 KB Output is correct
60 Correct 3692 ms 502428 KB Output is correct
61 Correct 3570 ms 490156 KB Output is correct
62 Correct 2421 ms 491036 KB Output is correct
63 Correct 2404 ms 490468 KB Output is correct
64 Runtime error 3905 ms 501632 KB Execution killed with signal 11
65 Halted 0 ms 0 KB -