#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb push_back
#define ins insert
#define f first
#define s second
#define db 0
#define EPS (1e-7) //0.0000001 the value
#define PI (acos(-1))
#define MAXN (300006)
#define MAXK 26
#define MAXX 15000006
#define ll /*long long*/ int
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < ee; ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph push
#define btinpct(x) __builtin_popcountll(x)
#define p2(x) (1LL<<(x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
ll n,k,q,ans[MAXN]; vector<ll>d;
struct store {
int l, type, a, b, i;
} A[MAXN];
vector<store>types[MAXN];
spi Q[MAXN]; // location, time(a,b) with respects to above
struct rays {
int x=0, in=0, a=0, b=0; // x - point, influence, [a,b] (means inclusive)
void close(ll y) { assert(b==-1); b = y; }
}; vector<rays>neg,pos;
set <pi> ms;
int currind_pos[MAXN], currind_neg[MAXN];
struct node {
int s,e,m;
ll v, lv;
node *l, *r;
node(ll _S, ll _E) {
s = _S, e = _E, m = (s+e)/2;
v = -INF; lv = -INF;
if(s!=e) {
l = new node(s,m);
r = new node(m+1,e);
}
}
void update(ll x, ll y, ll nv) {
if(x>y)return;
if(s==x&&e==y) { v = max(v, nv); return; }
if(x>m) r->update(x,y,nv);
else if(y<=m) l->update(x,y,nv);
else l->update(x,m,nv), r->update(m+1,y,nv);
lv = max(l->v, r->v);
}
ll rmq(ll x) {
if(s==e||v>lv) return v;
if(x>m) return max(v,r->rmq(x));
else return max(v,l->rmq(x));
assert(0);
}
void reset() {
v = -INF;
if(s==e) return;
l->reset();
r->reset();
}
} *seg;
ll idx(ll x) { return lbd(d,x)-d.begin(); }
void solve() {
FOR(i,0,n) types[A[i].type].pb(A[i]);
FOR(K,1,k+1) {
if(types[K].empty()) continue;
// sort(all(types[K]), [] (store x, store y) { return x.l < y.l; } );
vector<spi>events; // year to carry out, open/close, index
for(auto i : types[K]) events.pb(spi(i.a,pi(0,i.i))), events.pb(spi(i.b,pi(1,i.i)));
sort(all(events)); ms.clear();
// insert dummy for neg, as well as ms
ms.ins(pi(-INF,n));
ms.ins(pi(INF,n+1));
for(auto i : types[K]) currind_pos[i.i]=currind_neg[i.i] = -1; currind_neg[n]=currind_pos[n] = currind_pos[n+1]=currind_neg[n+1] = -1;
for(auto i : events) {
ll year = i.f, ind = i.s.s;
bool op = i.s.f; ll x = A[ind].l;
if(op == 0) { // open
auto itr = ms.ins(pi(x,ind));
auto itr2 = next(itr);
--itr;
// itr -> prev x, itr2 -> next x
/* neg rays */
// close ray from next to prev, set end time to (year - 1);
// open ray from curr to prev, set start time to (year);
// open ray from next to curr, set start time to (year);
ll ci = currind_neg[itr2->s];
if(ci == -1) { }
else neg[ci].close(year-1); // close ray from next to prev, set end time to (year - 1);
currind_neg[ind] = (int)neg.size(); // open ray from curr to prev, set start time to (year);
neg.pb({x,x-(x-itr->f)/2,year,-1});
// cerr << ind << ' ' << currind[ind] << '\n';
if(itr2->s < n) {
currind_neg[itr2->s] = (int)neg.size(); // open ray from next to curr, set start time to (year);
neg.pb({itr2->f, itr2->f-(itr2->f-x)/2,year,-1});
}
/* */
/* pos rays */
// close ray from prev to next, set end time to (year-1);
// open ray from prev to curr, set start time to (year);
// open ray from curr to next, set start time to (year);
ci = currind_pos[itr->s];
if(ci == -1) { }
else pos[ci].close(year-1); // close ray from prev to next, set end time to (year-1);
if(itr->s < n) {
currind_pos[itr->s] = (int)pos.size();
pos.pb({itr->f,itr->f+(x-itr->f)/2,year,-1}); // open ray from prev to curr, set start time to (year);
}
currind_pos[ind] = (int)pos.size();
pos.pb({x,x+(itr2->f-x)/2,year,-1}); // open ray from curr to next, set start time to (year);
/* */
} else {
auto itr2 = ms.erase(ms.find(pi(x,ind)));
auto itr = prev(itr2);
/* neg rays */
// close ray from curr to prev, end time: year
// close ray from next to curr, end time: year
// open ray from next to prev, start time: year+1
ll ci = currind_neg[ind];
neg[ci].close(year); // close ray from curr to prev, end time: year
ci = currind_neg[itr2->s]; if(0)cerr << ci << ' ' << neg.size() << ' ' << itr2->s << '\n';
if(ci == -1) {}
else neg[ci].close(year); // close ray from next to curr, end time: year
if(itr2->s < n) {
currind_neg[itr2->s] = (int)neg.size();
neg.pb({itr2->f, itr2->f-(itr2->f-itr->f)/2,year+1,-1}); // open ray from next to prev, start time: year+1
}
/* */
/* pos rays */
// close ray from prev to curr, end time: year
// close ray from curr to next, end time: year
// open ray from prev to next, start time: year+1
ci = currind_pos[itr->s];
if(ci == -1) { }
else pos[ci].close(year); // close ray from prev to curr, end time: year
ci = currind_pos[ind];
assert(ci!=-1);
pos[ci].close(year); // close ray from curr to next, end time: year
if(itr->s < n) {
currind_pos[itr->s] = (int)pos.size();
pos.pb({itr->f,itr->f+(itr2->f-itr->f)/2,year+1,-1}); // open ray from prev to next, start time: year+1
}
/* */
}
}
for(auto i : types[K]) currind_neg[i.i]=currind_pos[i.i] = 0; currind_pos[n] = currind_pos[n+1] = 0; currind_neg[n]=currind_neg[n+1]=0;
}
for(auto &i : neg) if(i.b == -1) i.b = INF;
for(auto &i : pos) if(i.b == -1) i.b = INF;
// for(auto &i : neg) cerr << i.x << ' ' << i.in << ' ' << i.a << ' ' << i.b << '\n';
// for(auto &i : pos) cerr << i.x << ' ' << i.in << ' ' << i.a << ' ' << i.b << '\n';
if(0) { FOR(i,0,n) d.pb(A[i].a), d.pb(A[i].b); } for(auto i : neg) d.pb(i.a),d.pb(i.b); for(auto i : pos) d.pb(i.a), d.pb(i.b);
d.pb(-INF); d.pb(INF);
sort(all(d)); d.resize(unique(all(d))-d.begin());
seg=new node(0,siz(d)-1);
sort(Q,Q+q);
sort(all(neg), [] (rays x, rays y) { return x.in < y.in; });
ll co = 0;
FOR(i,0,q) {
ll l = Q[i].f, t = Q[i].s.f; ll ind = Q[i].s.s;
while(co < neg.size() && neg[co].in <= l) {
seg->update(idx(neg[co].a), idx(neg[co].b), neg[co].x);
++co;
}
ans[ind]=seg->rmq(idx(t))-l;
}
if(0) seg=new node(0,siz(d)-1); seg->reset();
co = 0;
sort(all(pos), [] (rays x, rays y) { return x.in > y.in; });
// reverse(Q,Q+q);
for(ll i=q-1;i>=0;--i) {
ll l = Q[i].f, t = Q[i].s.f, ind = Q[i].s.s;
while(co < pos.size() && pos[co].in >= l) {
seg->update(idx(pos[co].a), idx(pos[co].b), -pos[co].x);
++co;
}
ans[ind]=max(ans[ind],seg->rmq(idx(t))+l);
}
return;
}
int main()
{
FAST
cin>>n>>k>>q;
FOR(i,0,n) { cin>>A[i].l>>A[i].type>>A[i].a>>A[i].b; A[i].i = i; }
FOR(i,0,q) {cin>>Q[i].f>>Q[i].s.f;Q[i].s.s=i;}
// FOR(i,0,n) d.pb(A[i].a), d.pb(A[i].b);
FOR(i,0,q) d.pb(Q[i].s.f);
// sort(all(d)); d.resize(unique(all(d))-d.begin());
solve(); // get_neg_rays, & pos_rays;
// check for -1 case here i guess:
#define storeco currind_pos
mmst(storeco,0);
sort(Q,Q+q,[](spi x, spi y){return x.s.f < y.s.f; });
sort(A,A+n,[](store x, store y){return x.a<y.a;});
ll co = 0; multiset <pi> ms; multiset <int> deci; FOR(i,1,k+1) deci.ins(0);
FOR(i,0,q) {
ll l=Q[i].f,t=Q[i].s.f,ind=Q[i].s.s;
while(co < n && A[co].a <= t) {
ms.ins(pi(A[co].b, A[co].type));
deci.erase(deci.find(storeco[A[co].type]));
storeco[A[co].type] ++;
deci.ins(storeco[A[co].type]);
++co;
}
while(ms.size() && ms.begin()->f < t) {
deci.erase(deci.find(storeco[ms.begin()->s]));
storeco[ms.begin()->s] --;
deci.ins(storeco[ms.begin()->s]);
ms.erase(ms.begin());
}
if(*deci.begin() == 0) ans[ind] = -1;
}
FOR(i,0,q) cout << ans[i] << '\n';
}
/*
*
2 1 1
5 1 1 5
4 1 1 4
5 3
*/
Compilation message
new_home.cpp: In function 'void solve()':
new_home.cpp:91:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(auto i : types[K]) currind_pos[i.i]=currind_neg[i.i] = -1; currind_neg[n]=currind_pos[n] = currind_pos[n+1]=currind_neg[n+1] = -1;
^~~
new_home.cpp:91:66: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(auto i : types[K]) currind_pos[i.i]=currind_neg[i.i] = -1; currind_neg[n]=currind_pos[n] = currind_pos[n+1]=currind_neg[n+1] = -1;
^~~~~~~~~~~
new_home.cpp:97:25: error: no matching function for call to 'next(std::pair<std::_Rb_tree_const_iterator<std::pair<int, int> >, bool>&)'
auto itr2 = next(itr);
^
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from new_home.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note: candidate: template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
next(_ForwardIterator __x, typename
^~~~
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note: template argument deduction/substitution failed:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h: In substitution of 'template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type) [with _ForwardIterator = std::pair<std::_Rb_tree_const_iterator<std::pair<int, int> >, bool>]':
new_home.cpp:97:25: required from here
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: error: no type named 'difference_type' in 'struct std::iterator_traits<std::pair<std::_Rb_tree_const_iterator<std::pair<int, int> >, bool> >'
new_home.cpp:98:5: error: no match for 'operator--' (operand type is 'std::pair<std::_Rb_tree_const_iterator<std::pair<int, int> >, bool>')
--itr;
^~~~~
new_home.cpp:110:23: error: base operand of '->' has non-pointer type 'std::pair<std::_Rb_tree_const_iterator<std::pair<int, int> >, bool>'
neg.pb({x,x-(x-itr->f)/2,year,-1});
^~
new_home.cpp:110:38: error: no matching function for call to 'std::vector<rays>::push_back(<brace-enclosed initializer list>)'
neg.pb({x,x-(x-itr->f)/2,year,-1});
^
In file included from /usr/include/c++/7/vector:64:0,
from /usr/include/c++/7/queue:61,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
from new_home.cpp:1:
/usr/include/c++/7/bits/stl_vector.h:939:7: note: candidate: void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = rays; _Alloc = std::allocator<rays>; std::vector<_Tp, _Alloc>::value_type = rays]
push_back(const value_type& __x)
^~~~~~~~~
/usr/include/c++/7/bits/stl_vector.h:939:7: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type& {aka const rays&}'
/usr/include/c++/7/bits/stl_vector.h:953:7: note: candidate: void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = rays; _Alloc = std::allocator<rays>; std::vector<_Tp, _Alloc>::value_type = rays]
push_back(value_type&& __x)
^~~~~~~~~
/usr/include/c++/7/bits/stl_vector.h:953:7: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<rays>::value_type&& {aka rays&&}'
new_home.cpp:114:53: error: no matching function for call to 'std::vector<rays>::push_back(<brace-enclosed initializer list>)'
neg.pb({itr2->f, itr2->f-(itr2->f-x)/2,year,-1});
^
In file included from /usr/include/c++/7/vector:64:0,
from /usr/include/c++/7/queue:61,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
from new_home.cpp:1:
/usr/include/c++/7/bits/stl_vector.h:939:7: note: candidate: void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = rays; _Alloc = std::allocator<rays>; std::vector<_Tp, _Alloc>::value_type = rays]
push_back(const value_type& __x)
^~~~~~~~~
/usr/include/c++/7/bits/stl_vector.h:939:7: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type& {aka const rays&}'
/usr/include/c++/7/bits/stl_vector.h:953:7: note: candidate: void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = rays; _Alloc = std::allocator<rays>; std::vector<_Tp, _Alloc>::value_type = rays]
push_back(value_type&& __x)
^~~~~~~~~
/usr/include/c++/7/bits/stl_vector.h:953:7: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<rays>::value_type&& {aka rays&&}'
new_home.cpp:121:25: error: base operand of '->' has non-pointer type 'std::pair<std::_Rb_tree_const_iterator<std::pair<int, int> >, bool>'
ci = currind_pos[itr->s];
^~
new_home.cpp:125:11: error: base operand of '->' has non-pointer type 'std::pair<std::_Rb_tree_const_iterator<std::pair<int, int> >, bool>'
if(itr->s < n) {
^~
new_home.cpp:126:21: error: base operand of '->' has non-pointer type 'std::pair<std::_Rb_tree_const_iterator<std::pair<int, int> >, bool>'
currind_pos[itr->s] = (int)pos.size();
^~
new_home.cpp:127:17: error: base operand of '->' has non-pointer type 'std::pair<std::_Rb_tree_const_iterator<std::pair<int, int> >, bool>'
pos.pb({itr->f,itr->f+(x-itr->f)/2,year,-1}); // open ray from prev to curr, set start time to (year);
^~
new_home.cpp:127:24: error: base operand of '->' has non-pointer type 'std::pair<std::_Rb_tree_const_iterator<std::pair<int, int> >, bool>'
pos.pb({itr->f,itr->f+(x-itr->f)/2,year,-1}); // open ray from prev to curr, set start time to (year);
^~
new_home.cpp:127:34: error: base operand of '->' has non-pointer type 'std::pair<std::_Rb_tree_const_iterator<std::pair<int, int> >, bool>'
pos.pb({itr->f,itr->f+(x-itr->f)/2,year,-1}); // open ray from prev to curr, set start time to (year);
^~
new_home.cpp:127:49: error: no matching function for call to 'std::vector<rays>::push_back(<brace-enclosed initializer list>)'
pos.pb({itr->f,itr->f+(x-itr->f)/2,year,-1}); // open ray from prev to curr, set start time to (year);
^
In file included from /usr/include/c++/7/vector:64:0,
from /usr/include/c++/7/queue:61,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
from new_home.cpp:1:
/usr/include/c++/7/bits/stl_vector.h:939:7: note: candidate: void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = rays; _Alloc = std::allocator<rays>; std::vector<_Tp, _Alloc>::value_type = rays]
push_back(const value_type& __x)
^~~~~~~~~
/usr/include/c++/7/bits/stl_vector.h:939:7: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type& {aka const rays&}'
/usr/include/c++/7/bits/stl_vector.h:953:7: note: candidate: void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = rays; _Alloc = std::allocator<rays>; std::vector<_Tp, _Alloc>::value_type = rays]
push_back(value_type&& __x)
^~~~~~~~~
/usr/include/c++/7/bits/stl_vector.h:953:7: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<rays>::value_type&& {aka rays&&}'
new_home.cpp:131:39: error: no matching function for call to 'std::vector<rays>::push_back(<brace-enclosed initializer list>)'
pos.pb({x,x+(itr2->f-x)/2,year,-1}); // open ray from curr to next, set start time to (year);
^
In file included from /usr/include/c++/7/vector:64:0,
from /usr/include/c++/7/queue:61,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
from new_home.cpp:1:
/usr/include/c++/7/bits/stl_vector.h:939:7: note: candidate: void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = rays; _Alloc = std::allocator<rays>; std::vector<_Tp, _Alloc>::value_type = rays]
push_back(const value_type& __x)
^~~~~~~~~
/usr/include/c++/7/bits/stl_vector.h:939:7: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type& {aka const rays&}'
/usr/include/c++/7/bits/stl_vector.h:953:7: note: candidate: void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = rays; _Alloc = std::allocator<rays>; std::vector<_Tp, _Alloc>::value_type = rays]
push_back(value_type&& __x)
^~~~~~~~~
/usr/include/c++/7/bits/stl_vector.h:953:7: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<rays>::value_type&& {aka rays&&}'
new_home.cpp:171:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(auto i : types[K]) currind_neg[i.i]=currind_pos[i.i] = 0; currind_pos[n] = currind_pos[n+1] = 0; currind_neg[n]=currind_neg[n+1]=0;
^~~
new_home.cpp:171:65: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(auto i : types[K]) currind_neg[i.i]=currind_pos[i.i] = 0; currind_pos[n] = currind_pos[n+1] = 0; currind_neg[n]=currind_neg[n+1]=0;
^~~~~~~~~~~
new_home.cpp:186:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(co < neg.size() && neg[co].in <= l) {
~~~^~~~~~~~~~~~
new_home.cpp:192:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(0) seg=new node(0,siz(d)-1); seg->reset();
^~
new_home.cpp:192:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if(0) seg=new node(0,siz(d)-1); seg->reset();
^~~
new_home.cpp:198:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(co < pos.size() && pos[co].in >= l) {
~~~^~~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:224:6: warning: unused variable 'l' [-Wunused-variable]
ll l=Q[i].f,t=Q[i].s.f,ind=Q[i].s.s;
^
