#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
ms.ins(pi(x,ind));
auto itr = ms.find(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;
}
/* for when u need negative numbers too */
inline int ri() {
bool neg = false;
int res = 0;
char c = getchar_unlocked();
while (true) {
if (c=='-') break;
if ('0'<=c && c<='9') break;
c = getchar_unlocked();
}
if (c=='-') neg = true;
else res = c-'0';
while (true) {
c = getchar_unlocked();
if (c<'0' || c>'9') break;
res = (res<<1) + (res<<3) + (c-'0');
}
if (neg) return -res;
return res;
}
int main()
{
FAST
//cin>>n>>k>>q;
n=ri(),k=ri(),q=ri();
FOR(i,0,n) { A[i].l=ri(),A[i].type=ri(),A[i].a=ri(),A[i].b=ri();if(0)cin>>A[i].l>>A[i].type>>A[i].a>>A[i].b; A[i].i = i; }
FOR(i,0,q) {Q[i].f=ri(),Q[i].s.f=ri();if(0)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:172: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:172: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:187:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(co < neg.size() && neg[co].in <= l) {
~~~^~~~~~~~~~~~
new_home.cpp:193:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(0) seg=new node(0,siz(d)-1); seg->reset();
^~
new_home.cpp:193: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:199: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:246:6: warning: unused variable 'l' [-Wunused-variable]
ll l=Q[i].f,t=Q[i].s.f,ind=Q[i].s.s;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8576 KB |
Output is correct |
| 2 |
Correct |
14 ms |
8576 KB |
Output is correct |
| 3 |
Correct |
10 ms |
8576 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
8576 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8576 KB |
Output is correct |
| 2 |
Correct |
14 ms |
8576 KB |
Output is correct |
| 3 |
Correct |
10 ms |
8576 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
8576 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1745 ms |
109044 KB |
Output is correct |
| 2 |
Correct |
1616 ms |
114904 KB |
Output is correct |
| 3 |
Correct |
1471 ms |
105164 KB |
Output is correct |
| 4 |
Correct |
1763 ms |
106744 KB |
Output is correct |
| 5 |
Correct |
1964 ms |
114052 KB |
Output is correct |
| 6 |
Correct |
1598 ms |
114440 KB |
Output is correct |
| 7 |
Correct |
1042 ms |
104892 KB |
Output is correct |
| 8 |
Correct |
1163 ms |
105116 KB |
Output is correct |
| 9 |
Correct |
1298 ms |
110620 KB |
Output is correct |
| 10 |
Correct |
1272 ms |
115492 KB |
Output is correct |
| 11 |
Correct |
1096 ms |
112160 KB |
Output is correct |
| 12 |
Correct |
1180 ms |
114040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4699 ms |
169596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8576 KB |
Output is correct |
| 2 |
Correct |
14 ms |
8576 KB |
Output is correct |
| 3 |
Correct |
10 ms |
8576 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
8576 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8576 KB |
Output is correct |
| 2 |
Correct |
14 ms |
8576 KB |
Output is correct |
| 3 |
Correct |
10 ms |
8576 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
8576 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
