#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<pii, pii> pi4;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=300020, LOG=20;
vector<pair<int*, int>> todo;
struct SEGMENT{
int seg[MAXN<<1];
SEGMENT(){
memset(seg, -31, sizeof(seg));
}
int upd(int pos, int val){
if (seg[pos]>=val) return 0;
todo.pb({seg+pos, seg[pos]});
seg[pos]=val;
return 1;
}
int Maximize(int l, int r, int val){
int res=0;
for (l+=MAXN, r+=MAXN; l<r; l>>=1, r>>=1){
if (l&1) res+=upd(l++, val);
if (r&1) res+=upd(--r, val);
}
return res;
}
int Get(int pos){
int res=seg[0];
for (pos+=MAXN; pos; pos>>=1) res=max(res, seg[pos]);
return res;
}
} seg1, seg2;
inline void undo(){
(*todo.back().first)=todo.back().second;
todo.pop_back();
}
int n, m, k, u, v, x, y, t, a, b, timer;
int typ[MAXN], X[MAXN], T[MAXN], A[MAXN], B[MAXN], L[MAXN], Y[MAXN];
int ans[MAXN];
vector<int> Q1[MAXN], Q2[MAXN], Q[MAXN];
vector<pi4> seg[MAXN<<2];
vector<int> compt={0, inf}, compx={0, inf+1};
multiset<int> st[MAXN];
map<pi4, int> mp;
void Add(int id, int tl, int tr, int l, int r, pi4 p){
// if (id==1) cerr<<"event in times:"<<l<<","<<r<<" : ["<<p.first.first<<", "<<p.first.second<<") "<<p.second.first<<' '<<p.second.second<<endl;
if (r<=tl || tr<=l) return ;
if (l<=tl && tr<=r){
seg[id].pb(p);
return ;
}
int mid=(tl+tr)>>1;
Add(id<<1, tl, mid, l, r, p);
Add(id<<1 | 1, mid, tr, l, r, p);
}
inline void f(pi4 p){
if (!mp.count(p)) mp[p]=timer;
else{
Add(1, 0, MAXN, mp[p], timer, p);
mp.erase(p);
}
}
inline void add(multiset<int> &st, int typ, int x){
// cerr<<"add in time "<<timer<<" : "<<typ<<", "<<x<<endl;
if (st.count(x)){
st.insert(x);
return ;
}
st.insert(x);
auto it=st.find(x);
int prv=*--it, nxt=*++++it;
f({{prv, (prv+nxt+1)/2}, {typ, 1}});
f({{(prv+nxt+1)/2, nxt+1}, {typ, 2}});
f({{prv, (prv+x+1)/2}, {typ, 1}});
f({{(prv+x+1)/2, x+1}, {typ, 2}});
f({{x, (x+nxt+1)/2}, {typ, 1}});
f({{(x+nxt+1)/2, nxt+1}, {typ, 2}});
}
inline void rem(multiset<int> &st, int typ, int x){
// cerr<<"rem in time "<<timer<<" : "<<typ<<", "<<x<<endl;
st.erase(st.find(x));
if (st.count(x)) return ;
auto it=st.lower_bound(x);
int nxt=*it, prv=*--it;
f({{prv, (prv+nxt+1)/2}, {typ, 1}});
f({{(prv+nxt+1)/2, nxt+1}, {typ, 2}});
f({{prv, (prv+x+1)/2}, {typ, 1}});
f({{(prv+x+1)/2, x+1}, {typ, 2}});
f({{x, (x+nxt+1)/2}, {typ, 1}});
f({{(x+nxt+1)/2, nxt+1}, {typ, 2}});
}
inline int gt(int x){
return lower_bound(all(compx), x)-compx.begin();
}
void dfs(int id, int tl, int tr){
int ted=0;
for (pi4 p:seg[id]){
if (p.second.second==1) ted+=seg1.Maximize(gt(p.first.first), gt(p.first.second), -p.first.first);
if (p.second.second==2) ted+=seg2.Maximize(gt(p.first.first), gt(p.first.second), p.first.second-1);
}
if (tr-tl==1){
for (int i:Q[tl]){
ans[i]=max(ans[i], L[i]+seg1.Get(gt(L[i])));
// debug(ans[i])
ans[i]=max(ans[i], seg2.Get(gt(L[i]))-L[i]);
if (ans[i]>100000000) ans[i]=-1;
}
}
else{
int mid=(tl+tr)>>1;
dfs(id<<1, tl, mid);
dfs(id<<1 | 1, mid, tr);
}
while (ted--) undo();
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin>>n>>k>>m;
for (int i=1; i<=k; i++){
st[i].insert(-inf);
st[i].insert(inf);
f({{0, inf+1}, {i, 2}});
f({{-inf, 0}, {i, 1}});
}
for (int i=1; i<=n; i++) cin>>X[i]>>T[i]>>A[i]>>B[i], B[i]++;
for (int i=1; i<=m; i++){
cin>>L[i]>>Y[i];
Y[i]=1;
compx.pb(L[i]);
compt.pb(Y[i]);
}
sort(all(compx));
sort(all(compt));
compx.resize(unique(all(compx))-compx.begin());
compt.resize(unique(all(compt))-compt.begin());
// debugv(compx)
for (int i=1; i<=n; i++){
A[i]=lower_bound(all(compt), A[i])-compt.begin();
B[i]=lower_bound(all(compt), B[i])-compt.begin();
// debug2(A[i], B[i])
Q1[A[i]].pb(i);
Q2[B[i]].pb(i);
}
for (int i=1; i<=m; i++){
Y[i]=lower_bound(all(compt), Y[i])-compt.begin();
Q[Y[i]].pb(i);
}
for (timer=0; timer<MAXN; timer++){
for (int i:Q1[timer]) add(st[T[i]], T[i], X[i]);
for (int i:Q2[timer]) rem(st[T[i]], T[i], X[i]);
}
while (mp.size()) f(mp.begin()->first);
dfs(1, 0, MAXN);
for (int i=1; i<=m; i++) cout<<ans[i]<<'\n';
return 0;
}
/*
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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
68472 KB |
Output is correct |
| 2 |
Correct |
51 ms |
68480 KB |
Output is correct |
| 3 |
Correct |
53 ms |
68472 KB |
Output is correct |
| 4 |
Incorrect |
52 ms |
68472 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
68472 KB |
Output is correct |
| 2 |
Correct |
51 ms |
68480 KB |
Output is correct |
| 3 |
Correct |
53 ms |
68472 KB |
Output is correct |
| 4 |
Incorrect |
52 ms |
68472 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5080 ms |
165916 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5067 ms |
152168 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
68472 KB |
Output is correct |
| 2 |
Correct |
51 ms |
68480 KB |
Output is correct |
| 3 |
Correct |
53 ms |
68472 KB |
Output is correct |
| 4 |
Incorrect |
52 ms |
68472 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
68472 KB |
Output is correct |
| 2 |
Correct |
51 ms |
68480 KB |
Output is correct |
| 3 |
Correct |
53 ms |
68472 KB |
Output is correct |
| 4 |
Incorrect |
52 ms |
68472 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
