#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 ;
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 %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] ) ;
}
/*
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:168:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
168 | scanf("%d%d%d", &N , &K , &Q ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:172:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
172 | scanf("%d%d%d%d", &x, &t, &a, &b ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:303:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
303 | scanf("%d%d", &l, &y ) ;
| ~~~~~^~~~~~~~~~~~~~~~~
new_home.cpp:189:52: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
189 | int l = 0 , r = sz(compressionX) - 1 , mid ;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
42628 KB |
Output is correct |
| 2 |
Incorrect |
30 ms |
42620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
42628 KB |
Output is correct |
| 2 |
Incorrect |
30 ms |
42620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2468 ms |
403024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3808 ms |
499416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
42628 KB |
Output is correct |
| 2 |
Incorrect |
30 ms |
42620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
42628 KB |
Output is correct |
| 2 |
Incorrect |
30 ms |
42620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
