#include <bits/stdc++.h>
#pragma optimize("unroll-loops")
#pragma optimize("Ofast")
const int N = 300013;
using namespace std;
struct Store{
int x, ty, a, b;
};
struct Query{
int t, ty, x, id;
};
struct Pair{
Pair() = default;
Pair(int _x, int _y, int _d) : x(_x), y(_y), d(_d){};
int x, y, d;
};
struct DS{
vector<int> sp[N * 2], bits[N * 2];
string name;
DS() = default;
DS(string _n) : name(_n){}
void insert(Pair p){
int x = p.x + 1, y = p.y + 1;
for(int i = x; i < N * 2; i += i & -i){
sp[i].push_back(y);
}
}
void parse(){
for(int i = 0; i < N * 2; i++) sp[i].push_back(0);
for(int i = 0; i < N * 2; i++){
sort(sp[i].begin(), sp[i].end());
sp[i].resize(unique(sp[i].begin(), sp[i].end()) - sp[i].begin());
bits[i].resize(sp[i].size());
}
}
void add(Pair p){
int x = p.x + 1, y = p.y + 1;
for(int i = x; i < N * 2; i += i & -i){
int idx = lower_bound(sp[i].begin(), sp[i].end(), y) - sp[i].begin();
for(int j = idx; j < sp[i].size(); j += j & -j){
bits[i][j] += p.d;
}
}
}
int qry(int x, int y){
x++; y++;
int ret = 0;
for(int i = x; i; i -= i & -i){
int idx = upper_bound(sp[i].begin(), sp[i].end(), y) - 1 - sp[i].begin();
for(int j = idx; j; j -= j & -j){
ret += bits[i][j];
}
}
return ret;
}
int qry(int x1, int x2, int y1, int y2){
return qry(x2, y2) + qry(x1 - 1, y1 - 1) - qry(x2, y1 - 1) - qry(x1 - 1, y2);
}
} ds;
struct BIT{
int bit[N];
void add(int p, int v){
p++;
for(int i = p; i < N; i += i & -i){
bit[i] += v;
}
}
int qry(int p){
int ret = 0;
p++;
for(int i = p; i; i -= i & -i){
ret += bit[i];
}
return ret;
}
int qry(int l, int r){
return qry(r) - qry(l - 1);
}
} bit;
vector<Store> stores;
vector<Query> Q;
vector<Pair> C[N * 3], D[N * 3];
int m;
int p[N * 2];
int ans[N];
int n, k, q;
bool check(int x1, int x2){
int l = lower_bound(p, p + m, x1) - p;
int r = upper_bound(p, p + m, x2) - 1 - p;
int c1 = bit.qry(l, r);
int c2 = ds.qry(l, r, l, r);
assert(c1 - c2 >= 0 && c1 - c2 <= k);
return c1 - c2 == k;
}
int qry(int x){
int l = 0, r = 1e9;
while(l != r){
int mid = (l + r) / 2;
if(check(p[x] - mid, p[x] + mid)){
r = mid;
}else{
l = mid + 1;
}
}
return l >= 9e8 ? -1 : l;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> k >> q;
vector<int> sp;
for(int i = 0; i < n; i++){
int x, ty, a, b;
cin >> x >> ty >> a >> b;
stores.push_back({x, ty, a, b + 1});
}
for(int i = 0; i < q; i++){
int x, t;
cin >> x >> t;
Q.push_back({t, 2, x, i});
}
{
vector<int> xs;
for(auto st : stores){
xs.push_back(st.x);
}
for(auto q : Q){
xs.push_back(q.x);
}
sort(xs.begin(), xs.end());
xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
m = xs.size();
for(int i = 0; i < m; i++){
p[i] = xs[i];
}
map<int, int> M;
for(int i = 0; i < m; i++){
M[xs[i]] = i;
}
for(auto& st : stores){
st.x = M[st.x];
}
for(auto& q : Q){
q.x = M[q.x];
}
}
for(auto st : stores){
Q.push_back({st.a, 1, st.x, st.ty});
Q.push_back({st.b + 1, 0, st.x, st.ty});
}
sort(Q.begin(), Q.end(), [](Query a, Query b){
return a.t < b.t || a.t == b.t && a.ty < b.ty;
});
multiset<int> vset[N];
for(int i = 0; i < Q.size(); i++){
Query q = Q[i];
auto ptr = vset[q.id].begin();
switch(q.ty){
case 0:
ptr = vset[q.id].lower_bound(q.x);
assert(ptr != vset[q.id].end());
if(ptr != vset[q.id].begin()) C[i].push_back({*prev(ptr), *ptr, -1});
if(next(ptr) != vset[q.id].end()) C[i].push_back({*ptr, *next(ptr), -1});
if(ptr != vset[q.id].begin() && next(ptr) != vset[q.id].end()) C[i].push_back({*prev(ptr), *next(ptr), 1});
D[i].push_back({q.x, -1, -1});
vset[q.id].erase(ptr);
break;
case 1:
ptr = vset[q.id].lower_bound(q.x);
if(ptr != vset[q.id].end() && ptr != vset[q.id].begin()) C[i].push_back({*prev(ptr), *ptr, -1});
if(ptr != vset[q.id].end()) C[i].push_back({q.x, *ptr, 1});
if(ptr != vset[q.id].begin()) C[i].push_back({*prev(ptr), q.x, 1});
D[i].push_back({q.x, -1, 1});
vset[q.id].insert(q.x);
break;
case 2:
break;
default:
assert(false);
}
}
for(int i = 0; i < Q.size(); i++){
for(auto p : C[i]){
ds.insert(p);
}
}
ds.parse();
for(int i = 0; i < Q.size(); i++){
for(auto p : C[i]){
ds.add(p);
}
for(auto p : D[i]){
bit.add(p.x, p.d);
}
Query q = Q[i];
switch(q.ty){
case 0:
break;
case 1:
break;
case 2: ans[q.id] = qry(q.x); break;
default: assert(false);
}
}
for(int i = 0; i < q; i++){
cout << ans[i] << '\n';
}
}
Compilation message
new_home.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
2 | #pragma optimize("unroll-loops")
|
new_home.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
3 | #pragma optimize("Ofast")
|
new_home.cpp: In member function 'void DS::add(Pair)':
new_home.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int j = idx; j < sp[i].size(); j += j & -j){
| ~~^~~~~~~~~~~~~~
new_home.cpp: In lambda function:
new_home.cpp:163:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
163 | return a.t < b.t || a.t == b.t && a.ty < b.ty;
| ~~~~~~~~~~~^~~~~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:166:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
166 | for(int i = 0; i < Q.size(); i++){
| ~~^~~~~~~~~~
new_home.cpp:193:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
193 | for(int i = 0; i < Q.size(); i++){
| ~~^~~~~~~~~~
new_home.cpp:199:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
199 | for(int i = 0; i < Q.size(); i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
122416 KB |
Output is correct |
| 2 |
Correct |
100 ms |
122396 KB |
Output is correct |
| 3 |
Correct |
99 ms |
122408 KB |
Output is correct |
| 4 |
Correct |
100 ms |
122436 KB |
Output is correct |
| 5 |
Incorrect |
114 ms |
122848 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
122416 KB |
Output is correct |
| 2 |
Correct |
100 ms |
122396 KB |
Output is correct |
| 3 |
Correct |
99 ms |
122408 KB |
Output is correct |
| 4 |
Correct |
100 ms |
122436 KB |
Output is correct |
| 5 |
Incorrect |
114 ms |
122848 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3139 ms |
501860 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4851 ms |
623076 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
122416 KB |
Output is correct |
| 2 |
Correct |
100 ms |
122396 KB |
Output is correct |
| 3 |
Correct |
99 ms |
122408 KB |
Output is correct |
| 4 |
Correct |
100 ms |
122436 KB |
Output is correct |
| 5 |
Incorrect |
114 ms |
122848 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
98 ms |
122416 KB |
Output is correct |
| 2 |
Correct |
100 ms |
122396 KB |
Output is correct |
| 3 |
Correct |
99 ms |
122408 KB |
Output is correct |
| 4 |
Correct |
100 ms |
122436 KB |
Output is correct |
| 5 |
Incorrect |
114 ms |
122848 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
