oj.uz

Submission #294995

# Submission time Handle Problem Language Result Execution time Memory
294995 2020-09-09T11:51:30 Z CaroLinda New Home (APIO18_new_home) C++14
47 / 100
 5000 ms 546484 KB 
#include <bits/stdc++.h>

#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
{

    vector<Event> tree[MAXN*2] ;

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

    void insertEvent(int a, int b, int c, int t1, int t2,  Event e)
    {

        vector< tiii > vec ;
        vec.pb( mkt(a,b,c) ) ;
        int ini = 0 ;

        while(ini < sz(vec))
        {

            int pos = get<0>( vec[ini] ) ;
            int l = get<1>( vec[ini] ) ;
            int r = get<2>( vec[ini] );
            ini++ ;

            if( l > t2 || r < t1 ) continue ;

            if(e.type > 0 && !(l >= t1 && r <= t2) ) tree[pos].pb(e) ;
            if(l >= t1 && r <= t2) tree[pos].pb(e) ;
            else
            {
                vec.pb( mkt(pos+1, l,m(l,r)) ) ;
                vec.pb( mkt( pos + ( m(l,r)-l+1 )*2 , m(l,r)+1, r ) ) ;
            }

        }

    }

    void solve(int a, int b, int c , int forbiddenType )
    {

        vector< tiii > vec ;
        vec.pb( mkt(a,b,c) ) ;
        int ini = 0 ;

        while(ini < sz(vec))
        {
            int pos = get<0>(vec[ini]) ;
            int l = get<1>( vec[ini] ) ;
            int r = get<2>( vec[ini] ) ;
            ini++ ;

            int mxNegative = -MAXT , mnPositive = MAXT ;

            for(auto e : tree[pos])
            {
                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 ) ;
                }
            }

            if(l == r) continue ;

            vec.pb( mkt(pos+1, l , m(l,r)) );
            vec.pb( mkt(pos+2*( m(l,r)-l+1 ) , m(l,r)+1, r ) ) ;

        }

    }

} 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 = 1 ;
    for(auto &e : compressionTime ) e.ss = Key++ ;

    for(auto e : sweep )
    {
        if(e.type == 0) continue ;
        seg.insertEvent( 1 , 1 , sz(compressionTime) , compressionTime[e.t1] , compressionTime[e.t2] , e ) ;
    }

    seg.solve(1,1, sz(compressionTime) , 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( 1 , 1 , sz(compressionTime) , compressionTime[e.t1] , compressionTime[e.t2] , e ) ;
    }

    seg.solve(1,1, sz(compressionTime) , -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:195:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  195 |     scanf("%d%d%d", &N , &K , &Q ) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:207:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  207 |         scanf("%d%d%d%d", &x, &t, &a, &b ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:259:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  259 |         scanf("%d%d", &l, &y ) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 113016 KB Output is correct
2 Correct 73 ms 113016 KB Output is correct
3 Correct 74 ms 113016 KB Output is correct
4 Correct 75 ms 113148 KB Output is correct
5 Correct 75 ms 113272 KB Output is correct
6 Correct 84 ms 113784 KB Output is correct
7 Correct 84 ms 113912 KB Output is correct
8 Correct 82 ms 113784 KB Output is correct
9 Correct 82 ms 114040 KB Output is correct
10 Correct 83 ms 113784 KB Output is correct
11 Correct 80 ms 113656 KB Output is correct
12 Correct 82 ms 113612 KB Output is correct
13 Correct 79 ms 113784 KB Output is correct
14 Correct 94 ms 113656 KB Output is correct
15 Correct 95 ms 113784 KB Output is correct
16 Correct 101 ms 113784 KB Output is correct
17 Correct 112 ms 113784 KB Output is correct
18 Correct 82 ms 113912 KB Output is correct
19 Correct 82 ms 113784 KB Output is correct
20 Correct 82 ms 113784 KB Output is correct
21 Correct 76 ms 113400 KB Output is correct
22 Correct 92 ms 113912 KB Output is correct
23 Correct 83 ms 113912 KB Output is correct
24 Correct 85 ms 113784 KB Output is correct
25 Correct 85 ms 113784 KB Output is correct
26 Correct 82 ms 113656 KB Output is correct
27 Correct 78 ms 113272 KB Output is correct
28 Correct 80 ms 113672 KB Output is correct
29 Correct 80 ms 113660 KB Output is correct
30 Correct 77 ms 113676 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 113016 KB Output is correct
2 Correct 73 ms 113016 KB Output is correct
3 Correct 74 ms 113016 KB Output is correct
4 Correct 75 ms 113148 KB Output is correct
5 Correct 75 ms 113272 KB Output is correct
6 Correct 84 ms 113784 KB Output is correct
7 Correct 84 ms 113912 KB Output is correct
8 Correct 82 ms 113784 KB Output is correct
9 Correct 82 ms 114040 KB Output is correct
10 Correct 83 ms 113784 KB Output is correct
11 Correct 80 ms 113656 KB Output is correct
12 Correct 82 ms 113612 KB Output is correct
13 Correct 79 ms 113784 KB Output is correct
14 Correct 94 ms 113656 KB Output is correct
15 Correct 95 ms 113784 KB Output is correct
16 Correct 101 ms 113784 KB Output is correct
17 Correct 112 ms 113784 KB Output is correct
18 Correct 82 ms 113912 KB Output is correct
19 Correct 82 ms 113784 KB Output is correct
20 Correct 82 ms 113784 KB Output is correct
21 Correct 76 ms 113400 KB Output is correct
22 Correct 92 ms 113912 KB Output is correct
23 Correct 83 ms 113912 KB Output is correct
24 Correct 85 ms 113784 KB Output is correct
25 Correct 85 ms 113784 KB Output is correct
26 Correct 82 ms 113656 KB Output is correct
27 Correct 78 ms 113272 KB Output is correct
28 Correct 80 ms 113672 KB Output is correct
29 Correct 80 ms 113660 KB Output is correct
30 Correct 77 ms 113676 KB Output is correct
31 Correct 4017 ms 267384 KB Output is correct
32 Correct 197 ms 123632 KB Output is correct
33 Correct 3316 ms 255572 KB Output is correct
34 Correct 3652 ms 255696 KB Output is correct
35 Correct 3800 ms 267172 KB Output is correct
36 Correct 3494 ms 266672 KB Output is correct
37 Correct 2485 ms 246348 KB Output is correct
38 Correct 2383 ms 246444 KB Output is correct
39 Correct 1762 ms 233528 KB Output is correct
40 Correct 1880 ms 236688 KB Output is correct
41 Correct 3368 ms 241368 KB Output is correct
42 Correct 3339 ms 242384 KB Output is correct
43 Correct 171 ms 122040 KB Output is correct
44 Correct 3259 ms 241060 KB Output is correct
45 Correct 3131 ms 233012 KB Output is correct
46 Correct 2808 ms 218172 KB Output is correct
47 Correct 1453 ms 217040 KB Output is correct
48 Correct 1393 ms 211828 KB Output is correct
49 Correct 1577 ms 223240 KB Output is correct
50 Correct 1717 ms 240624 KB Output is correct
51 Correct 1548 ms 218060 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 3896 ms 499232 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 73 ms 113016 KB Output is correct
2 Correct 73 ms 113016 KB Output is correct
3 Correct 74 ms 113016 KB Output is correct
4 Correct 75 ms 113148 KB Output is correct
5 Correct 75 ms 113272 KB Output is correct
6 Correct 84 ms 113784 KB Output is correct
7 Correct 84 ms 113912 KB Output is correct
8 Correct 82 ms 113784 KB Output is correct
9 Correct 82 ms 114040 KB Output is correct
10 Correct 83 ms 113784 KB Output is correct
11 Correct 80 ms 113656 KB Output is correct
12 Correct 82 ms 113612 KB Output is correct
13 Correct 79 ms 113784 KB Output is correct
14 Correct 94 ms 113656 KB Output is correct
15 Correct 95 ms 113784 KB Output is correct
16 Correct 101 ms 113784 KB Output is correct
17 Correct 112 ms 113784 KB Output is correct
18 Correct 82 ms 113912 KB Output is correct
19 Correct 82 ms 113784 KB Output is correct
20 Correct 82 ms 113784 KB Output is correct
21 Correct 76 ms 113400 KB Output is correct
22 Correct 92 ms 113912 KB Output is correct
23 Correct 83 ms 113912 KB Output is correct
24 Correct 85 ms 113784 KB Output is correct
25 Correct 85 ms 113784 KB Output is correct
26 Correct 82 ms 113656 KB Output is correct
27 Correct 78 ms 113272 KB Output is correct
28 Correct 80 ms 113672 KB Output is correct
29 Correct 80 ms 113660 KB Output is correct
30 Correct 77 ms 113676 KB Output is correct
31 Correct 4017 ms 267384 KB Output is correct
32 Correct 197 ms 123632 KB Output is correct
33 Correct 3316 ms 255572 KB Output is correct
34 Correct 3652 ms 255696 KB Output is correct
35 Correct 3800 ms 267172 KB Output is correct
36 Correct 3494 ms 266672 KB Output is correct
37 Correct 2485 ms 246348 KB Output is correct
38 Correct 2383 ms 246444 KB Output is correct
39 Correct 1762 ms 233528 KB Output is correct
40 Correct 1880 ms 236688 KB Output is correct
41 Correct 3368 ms 241368 KB Output is correct
42 Correct 3339 ms 242384 KB Output is correct
43 Correct 171 ms 122040 KB Output is correct
44 Correct 3259 ms 241060 KB Output is correct
45 Correct 3131 ms 233012 KB Output is correct
46 Correct 2808 ms 218172 KB Output is correct
47 Correct 1453 ms 217040 KB Output is correct
48 Correct 1393 ms 211828 KB Output is correct
49 Correct 1577 ms 223240 KB Output is correct
50 Correct 1717 ms 240624 KB Output is correct
51 Correct 1548 ms 218060 KB Output is correct
52 Correct 3821 ms 291648 KB Output is correct
53 Correct 3881 ms 274624 KB Output is correct
54 Correct 4008 ms 275840 KB Output is correct
55 Correct 3271 ms 256988 KB Output is correct
56 Correct 3512 ms 264296 KB Output is correct
57 Correct 3358 ms 245076 KB Output is correct
58 Correct 3458 ms 256836 KB Output is correct
59 Correct 3619 ms 266472 KB Output is correct
60 Correct 3433 ms 245560 KB Output is correct
61 Correct 368 ms 157284 KB Output is correct
62 Correct 3641 ms 291256 KB Output is correct
63 Correct 3878 ms 278016 KB Output is correct
64 Correct 3823 ms 271528 KB Output is correct
65 Correct 3717 ms 259480 KB Output is correct
66 Correct 3464 ms 244116 KB Output is correct
67 Correct 590 ms 152888 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 113016 KB Output is correct
2 Correct 73 ms 113016 KB Output is correct
3 Correct 74 ms 113016 KB Output is correct
4 Correct 75 ms 113148 KB Output is correct
5 Correct 75 ms 113272 KB Output is correct
6 Correct 84 ms 113784 KB Output is correct
7 Correct 84 ms 113912 KB Output is correct
8 Correct 82 ms 113784 KB Output is correct
9 Correct 82 ms 114040 KB Output is correct
10 Correct 83 ms 113784 KB Output is correct
11 Correct 80 ms 113656 KB Output is correct
12 Correct 82 ms 113612 KB Output is correct
13 Correct 79 ms 113784 KB Output is correct
14 Correct 94 ms 113656 KB Output is correct
15 Correct 95 ms 113784 KB Output is correct
16 Correct 101 ms 113784 KB Output is correct
17 Correct 112 ms 113784 KB Output is correct
18 Correct 82 ms 113912 KB Output is correct
19 Correct 82 ms 113784 KB Output is correct
20 Correct 82 ms 113784 KB Output is correct
21 Correct 76 ms 113400 KB Output is correct
22 Correct 92 ms 113912 KB Output is correct
23 Correct 83 ms 113912 KB Output is correct
24 Correct 85 ms 113784 KB Output is correct
25 Correct 85 ms 113784 KB Output is correct
26 Correct 82 ms 113656 KB Output is correct
27 Correct 78 ms 113272 KB Output is correct
28 Correct 80 ms 113672 KB Output is correct
29 Correct 80 ms 113660 KB Output is correct
30 Correct 77 ms 113676 KB Output is correct
31 Correct 4017 ms 267384 KB Output is correct
32 Correct 197 ms 123632 KB Output is correct
33 Correct 3316 ms 255572 KB Output is correct
34 Correct 3652 ms 255696 KB Output is correct
35 Correct 3800 ms 267172 KB Output is correct
36 Correct 3494 ms 266672 KB Output is correct
37 Correct 2485 ms 246348 KB Output is correct
38 Correct 2383 ms 246444 KB Output is correct
39 Correct 1762 ms 233528 KB Output is correct
40 Correct 1880 ms 236688 KB Output is correct
41 Correct 3368 ms 241368 KB Output is correct
42 Correct 3339 ms 242384 KB Output is correct
43 Correct 171 ms 122040 KB Output is correct
44 Correct 3259 ms 241060 KB Output is correct
45 Correct 3131 ms 233012 KB Output is correct
46 Correct 2808 ms 218172 KB Output is correct
47 Correct 1453 ms 217040 KB Output is correct
48 Correct 1393 ms 211828 KB Output is correct
49 Correct 1577 ms 223240 KB Output is correct
50 Correct 1717 ms 240624 KB Output is correct
51 Correct 1548 ms 218060 KB Output is correct
52 Execution timed out 5090 ms 546484 KB Time limit exceeded
53 Halted 0 ms 0 KB -