#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
//Note to self: Check for overflow
const int N=20'000'007;
int tag[N],L[N],R[N];
int idx=0;
vector<vector<pii>> stare;
vector<pii> empt;
int AddPos(int p, int l, int r, int ll, int rr, int x) //positive slope
{
if (ll>r || rr<l) return 0;
else if (ll<=l && rr>=r)
{
stare.back().pb({p,tag[p]});
tag[p]=max(tag[p],x);
return r-l+1;
}
else
{
int mid=(l+r)/2;
if (!L[p]) L[p]=++idx;
if (!R[p]) R[p]=++idx;
int siz=0;
siz+=AddPos(L[p],l,mid,ll,rr,x);
siz+=AddPos(R[p],mid+1,r,ll,rr,x+siz);
return siz;
}
}
int AddNeg(int p, int l, int r, int ll, int rr, int x) //negative slope
{
if (ll>r || rr<l) return 0;
else if (ll<=l && rr>=r)
{
stare.back().pb({p,tag[p]});
tag[p]=max(tag[p],x);
return r-l+1;
}
else
{
int mid=(l+r)/2;
if (!L[p]) L[p]=++idx;
if (!R[p]) R[p]=++idx;
int siz=0;
siz+=AddNeg(R[p],mid+1,r,ll,rr,x);
siz+=AddNeg(L[p],l,mid,ll,rr,x+siz);
return siz;
}
}
int MaxPos(int p, int l, int r, int s)
{
if (!p) return -mod;
int m=tag[p]+s-l;
int mid=(l+r)/2;
if (s<=mid) m=max(m,MaxPos(L[p],l,mid,s));
else m=max(m,MaxPos(R[p],mid+1,r,s));
return m;
}
int MaxNeg(int p, int l, int r, int s)
{
if (!p) return -mod;
int m=tag[p]+r-s;
int mid=(l+r)/2;
if (s<=mid) m=max(m,MaxNeg(L[p],l,mid,s));
else m=max(m,MaxNeg(R[p],mid+1,r,s));
return m;
}
void rollback()
{
for (auto [p,v] : stare.back()) tag[p]=v;
stare.popb();
}
void ispisi(int p, int l, int r)
{
if (!p) return;
if (l==r) return;
int mid=(l+r)/2;
ispisi(L[p],l,mid),ispisi(R[p],mid+1,r);
}
int ans[300005];
int k=1;
vector<pii> rmv[4444444];
int l[4444444],r[4444444];
vector<pii> qry[4444444]; //lokacija,index
void ToRmv(int p, int ll, int rr, int t, int x)
{
if (ll>r[p] || rr<l[p]) return;
if (ll<=l[p] && rr>=r[p]) rmv[p].pb({t,x});
else ToRmv(2*p,ll,rr,t,x),ToRmv(2*p+1,ll,rr,t,x);
}
multiset<int> gde[300005];
int LOSIH=0;
void dfs(int p)
{
int kolko=0;
for (auto [t,x] : rmv[p])
{
gde[t].erase(gde[t].find(x));
if (gde[t].empty()) LOSIH++;
auto desni=gde[t].lower_bound(x);
if (desni!=gde[t].end() && *desni==x) continue;
else if (desni==gde[t].end())
{
auto levi=prev(desni);
stare.pb(empt),AddPos(1,0,1e8,*levi,1e8,0),kolko++;
}
else if (desni==gde[t].begin())
{
stare.pb(empt),AddNeg(2,0,1e8,0,*desni,0),kolko++;
}
else
{
auto levi=prev(desni);
int a=*levi,b=*desni,pola=(b-a)/2;
stare.pb(empt),AddPos(1,0,1e8,a,a+pola,0),kolko++;
stare.pb(empt),AddNeg(2,0,1e8,b-pola,b,0),kolko++;
}
}
if (p<k) dfs(2*p),dfs(2*p+1);
else
{
for (auto [x,ind] : qry[p])
{
/*cout<<"("<<ind<<","<<x<<")"<<":"<<endl;
fff(i,1,2)
{
cout<<i<<": ";
for (auto it : gde[i]) cout<<it<<" ";
cout<<endl;
} cout<<endl;*/
if (LOSIH==0) ans[ind]=max(MaxPos(1,0,1e8,x),MaxNeg(2,0,1e8,x));
else ans[ind]=-1;
}
}
while (kolko--) rollback();
for (auto [t,x] : rmv[p])
{
if (gde[t].empty()) LOSIH--;
gde[t].insert(x);
}
}
int main()
{
FAST;
ff(i,0,N) tag[i]=-mod;
int n,TIPS,q; cin>>n>>TIPS>>q;
vector<int> kords;
vector<pair<pii,pii>> segs;
ff(i,0,n)
{
int x,t,a,b;
cin>>x>>t>>a>>b;
gde[t].insert(x);
segs.pb({{0,a-1},{t,x}});
segs.pb({{b+1,1e8},{t,x}});
kords.pb(a-1),kords.pb(b+1);
kords.pb(a),kords.pb(b);
}
vector<pii> queries;
ff(i,0,q)
{
int x,y; cin>>x>>y;
queries.pb({x,y});
kords.pb(y);
}
sort(all(kords));
kords.erase(unique(all(kords)),kords.end());
ff(i,0,(int)segs.size())
{
segs[i].xx.xx=lower_bound(all(kords),segs[i].xx.xx)-kords.begin();
segs[i].xx.yy=lower_bound(all(kords),segs[i].xx.yy)-kords.begin();
}
ff(i,0,(int)queries.size())
{
queries[i].yy=lower_bound(all(kords),queries[i].yy)-kords.begin();
}
//Build the DCT segtree
while (k<(int)kords.size()) k*=2;
ff(i,0,(int)kords.size()) l[i+k]=kords[i],r[i+k]=kords[i];
ff(i,(int)kords.size(),k) l[i+k]=mod,r[i+k]=mod;
bff(i,1,k) l[i]=l[2*i],r[i]=r[2*i+1];
ff(i,0,(int)queries.size()) qry[queries[i].yy+k].pb({queries[i].xx,i});
for (auto it : segs) ToRmv(1,it.xx.xx,it.xx.yy,it.yy.xx,it.yy.yy);
//Zavrsetak zadatka
idx=2;
fff(tip,1,TIPS) if (!gde[tip].empty())
{
vector<int> temp;
for (auto it : gde[tip]) temp.pb(it);
stare.pb(empt),AddNeg(2,0,1e8,0,temp[0],0);
ff(i,1,(int)temp.size())
{
int pola=(temp[i]-temp[i-1])/2;
stare.pb(empt),AddPos(1,0,1e8,temp[i-1],temp[i-1]+pola,0);
stare.pb(empt),AddNeg(2,0,1e8,temp[i]-pola,temp[i],0);
}
stare.pb(empt),AddPos(1,0,1e8,temp.back(),1e8,0);
}
dfs(1);
ff(i,0,q) cout<<ans[i]<<"\n";
}
//Note to self: Check for overflow
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7
1 1 1
100000000 1 1 1
1 1
*/
Compilation message
new_home.cpp: In function 'void rollback()':
new_home.cpp:114:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
114 | for (auto [p,v] : stare.back()) tag[p]=v;
| ^
new_home.cpp: In function 'void dfs(int)':
new_home.cpp:148:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
148 | for (auto [t,x] : rmv[p])
| ^
new_home.cpp:177:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
177 | for (auto [x,ind] : qry[p])
| ^
new_home.cpp:193:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
193 | for (auto [t,x] : rmv[p])
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
368 ms |
611020 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
368 ms |
611020 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2168 ms |
961356 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3617 ms |
1048576 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
368 ms |
611020 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
368 ms |
611020 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
