#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int*, int> INFO;
struct Mart{
int x, y, t; bool on; /// location, type, time
Mart(int x, int y, int t, bool on): x(x), y(y), t(t), on(on){}
bool operator<(const Mart &r)const{
return t<r.t;
}
};
struct Query{
int x, t, idx;
Query(){}
Query(int x, int t, int idx): x(x), t(t), idx(idx){}
bool operator<(const Query &r)const{
return t<r.t;
}
};
struct Segment{
int a, b, l, r, s, e;
Segment(){}
Segment(int a, int b, int l, int r, int s, int e): a(a), b(b), l(l), r(r), s(s), e(e){}
};
vector<Segment> segment;
struct maxSegmentTree{
vector<stack<INFO> > vec;
int tree[6000002], lazy[6000002];
void init(int i, int l, int r){
tree[i] = lazy[i] = -1e9;
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m), init(i*2+1, m+1, r);
}
inline void save(){
vec.push_back(stack<INFO> ());
}
void undo(){
while(!vec.back().empty()){
INFO tmp = vec.back().top();
*(tmp.first) = tmp.second;
vec.back().pop();
}
vec.pop_back();
}
#define saveinfo(A) vec.back().push(INFO {&A, A})
void propagate(int i, int l, int r){
if(tree[i] < lazy[i]){
saveinfo(tree[i]);
tree[i] = lazy[i];
}
if(l!=r){
if(lazy[i*2] < lazy[i]){
saveinfo(lazy[i*2]);
lazy[i*2] = lazy[i];
}
if(lazy[i*2+1] < lazy[i]){
saveinfo(lazy[i*2+1]);
lazy[i*2+1] = lazy[i];
}
}
}
void rangeMax(int i, int l, int r, int s, int e, int val){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
if(lazy[i] >= val) return;
saveinfo(lazy[i]);
lazy[i] = val;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
rangeMax(i*2, l, m, s, e, val);
rangeMax(i*2+1, m+1, r, s, e, val);
saveinfo(tree[i]);
tree[i] = max(tree[i*2], tree[i*2+1]);
}
int getVal(int i, int l, int r, int idx){
propagate(i, l, r);
if(l==r) return tree[i];
int m = (l+r)>>1;
if(idx <= m) return getVal(i*2, l, m, idx);
return getVal(i*2+1, m+1, r, idx);
}
} treeA, treeB;
int n, q, k;
void input();
void createQueries();
void renumber();
void ODCinit();
void ODC(int, int, vector<Segment>&);
void output();
int main(){
input();
createQueries();
renumber();
ODCinit();
ODC(1, n+q+1, segment);
output();
}
vector<Mart> vec;
vector<Query> qvec;
int ans[300002];
vector<int> tVec;
void input(){
scanf("%d %d %d", &n, &k, &q);
for(int i=1; i<=n; i++){
int x, t, a, b;
scanf("%d %d %d %d", &x, &t, &a, &b);
vec.push_back(Mart(x, t, a, 1));
vec.push_back(Mart(x, t, b+1, 0));
tVec.push_back(t);
}
sort(vec.begin(), vec.end());
for(int i=1; i<=q; i++){
int l, y;
scanf("%d %d", &l, &y);
qvec.push_back(Query(l, y, i));
tVec.push_back(y);
}
sort(qvec.begin(), qvec.end());
sort(tVec.begin(), tVec.end());
tVec.erase(unique(tVec.begin(), tVec.end()), tVec.end());
for(auto &p: vec) p.t = lower_bound(tVec.begin(), tVec.end(), p.t) - tVec.begin() + 1;
for(auto &p: qvec) p.t = lower_bound(tVec.begin(), tVec.end(), p.t) - tVec.begin() + 1;
}
multiset<int> mst[300002];
unordered_multimap<ll, int> mtm;
inline void addSegment(int l, int r, int t){
mtm.insert(make_pair(100000000LL * l + r, t));
}
void delSegment(int l, int r, int e){
auto it = mtm.find(100000000LL * l + r);
int s = it->second;
mtm.erase(it);
if(s>=e) return;
int mid = (l+r)/2;
segment.push_back(Segment(1, -l, l, mid, s, e-1));
segment.push_back(Segment(-1, r, mid+1, r, s, e-1));
}
void createQueries(){
int pnt = 0;
qvec.push_back(Query(0, 100000001, 0));
for(int i=1; i<=k; i++){
mst[i].insert(-300000000), mst[i].insert(400000000);
addSegment(-300000000, 400000000, 1);
}
for(int i=0; i<q+1; i++){
while(pnt < 2*n && vec[pnt].t <= qvec[i].t){
Mart tmp = vec[pnt++];
if(tmp.on){
auto it = mst[tmp.y].lower_bound(tmp.x);
int l = (it == mst[tmp.y].begin() ? -1 : *prev(it));
int r = (it == mst[tmp.y].end() ? -1 : *it);
mst[tmp.y].insert(tmp.x);
if(l!=-1 && r!=-1) delSegment(l, r, tmp.t);
if(l!=-1) addSegment(l, tmp.x, tmp.t);
if(r!=-1) addSegment(tmp.x, r, tmp.t);
}
else{
mst[tmp.y].erase(mst[tmp.y].find(tmp.x));
auto it = mst[tmp.y].lower_bound(tmp.x);
int l = (it == mst[tmp.y].begin() ? -1 : *prev(it));
int r = (it == mst[tmp.y].end() ? -1 : *it);
if(l!=-1 && r!=-1) addSegment(l, r, tmp.t);
if(l!=-1) delSegment(l, tmp.x, tmp.t);
if(r!=-1) delSegment(tmp.x, r, tmp.t);
}
}
}
for(int i=1; i<=k; i++){
delSegment(-300000000, 400000000, n+q+1);
}
assert(mtm.empty());
}
vector<int> renumberVec; int z;
void renumber(){
renumberVec.push_back(-300000000);
for(auto s: segment){
renumberVec.push_back(s.l);
renumberVec.push_back(s.r);
}
sort(renumberVec.begin(), renumberVec.end());
renumberVec.erase(unique(renumberVec.begin(), renumberVec.end()), renumberVec.end());
z = renumberVec.size();
assert(z <= 1500000);
}
inline int g(int x){
return upper_bound(renumberVec.begin(), renumberVec.end(), x) - renumberVec.begin() - 1;
}
int pnt = 0;
void ODCinit(){
treeA.init(1, 0, z-1);
treeB.init(1, 0, z-1);
}
void ODC(int l, int r, vector<Segment>& vec){
treeA.save(); treeB.save();
vector<Segment> lv, rv;
int m = (l+r)/2;
for(Segment s: vec){
if(s.s <= l && r <= s.e){
if(s.a == 1) treeA.rangeMax(1, 0, z-1, g(s.l), g(s.r)-1, s.b);
else treeB.rangeMax(1, 0, z-1, g(s.l), g(s.r)-1, s.b);
}
else{
if(s.s <= m) lv.push_back(s);
if(m < s.e) rv.push_back(s);
}
}
vec.clear();
vec.shrink_to_fit();
if(l==r){
while(pnt < q && qvec[pnt].t == l){
Query query = qvec[pnt++];
// printf("%d: %d %d\n", pnt, treeA.getVal(1, 0, z-1, g(query.x)), treeB.getVal(1, 0, z-1, g(query.x)));
ans[query.idx] = max(treeA.getVal(1, 0, z-1, g(query.x)) + query.x,
treeB.getVal(1, 0, z-1, g(query.x)) - query.x);
}
treeA.undo(); treeB.undo();
return;
}
if(pnt < q && qvec[pnt].t <= m) ODC(l, m, lv);
if(pnt < q && qvec[pnt].t <= r) ODC(m+1, r, rv);
treeA.undo(); treeB.undo();
}
void output(){
for(int i=1; i<=q; i++){
printf("%d\n", ans[i] > 100000000 ? -1 : ans[i]);
}
}
Compilation message
new_home.cpp: In function 'void input()':
new_home.cpp:124:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
124 | scanf("%d %d %d", &n, &k, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
127 | scanf("%d %d %d %d", &x, &t, &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:136:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
136 | scanf("%d %d", &l, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14412 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14428 KB |
Output is correct |
| 3 |
Correct |
10 ms |
14412 KB |
Output is correct |
| 4 |
Correct |
9 ms |
14412 KB |
Output is correct |
| 5 |
Incorrect |
12 ms |
14540 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14412 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14428 KB |
Output is correct |
| 3 |
Correct |
10 ms |
14412 KB |
Output is correct |
| 4 |
Correct |
9 ms |
14412 KB |
Output is correct |
| 5 |
Incorrect |
12 ms |
14540 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4065 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5155 ms |
1019484 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14412 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14428 KB |
Output is correct |
| 3 |
Correct |
10 ms |
14412 KB |
Output is correct |
| 4 |
Correct |
9 ms |
14412 KB |
Output is correct |
| 5 |
Incorrect |
12 ms |
14540 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
14412 KB |
Output is correct |
| 2 |
Correct |
9 ms |
14428 KB |
Output is correct |
| 3 |
Correct |
10 ms |
14412 KB |
Output is correct |
| 4 |
Correct |
9 ms |
14412 KB |
Output is correct |
| 5 |
Incorrect |
12 ms |
14540 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
