#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int lim = 5e6;
struct Node{
map<int, int> inc, dec;
Node *l = nullptr, *r = nullptr;
Node(){}
Node(Node *_l, Node *_r): l(_l), r(_r){}
}Nodes[lim];
int ls_node = 0;
Node* newNode(){
return &Nodes[ls_node++];
}
struct sparse_segtree{
Node* root = newNode();
int n = 1;
sparse_segtree(int _n){
while(n < _n) n*=2;
}
void add(int l, int r, Node* nd, int a, int b, ll x, bool inc){
if(a > r || b < l) return;
if(a >= l && b <= r){
if(inc) nd->inc[x+a-l]++;
else nd->dec[x-a+l]++;
return;
}
int m = (a+b)/2;
if(!nd->l) nd->l = newNode();
if(!nd->r) nd->r = newNode();
add(l, r, nd->l, a, m, x, inc);
add(l, r, nd->r, m+1, b, x, inc);
}
void add(int l, int r, int x, bool inc){
add(l, r, root, 0, n-1, x, inc);
}
void remove(int l, int r, Node* nd, int a, int b, int x, bool inc){
if(a > r || b < l) return;
if(a >= l && b <= r){
if(inc){
nd->inc[x+a-l]--;
if(nd->inc[x+a-l] == 0) nd->inc.erase(x+a-l);
}
else{
nd->dec[x-a+l]--;
if(nd->dec[x-a+l] == 0) nd->dec.erase(x-a+l);
}
return;
}
int m = (a+b)/2;
if(!nd->l) nd->l = new Node();
if(!nd->r) nd->r = new Node();
remove(l, r, nd->l, a, m, x, inc);
remove(l, r, nd->r, m+1, b, x, inc);
}
void remove(int l, int r, int x, bool inc){
remove(l, r, root, 0, n-1, x, inc);
}
int get(int i){
Node* nd = root;
int a = 0, b = n-1;
int mx = 0;
while(nd){
if(!nd->inc.empty()) mx = max(mx, nd->inc.rbegin()->first+i-a);
if(!nd->dec.empty()) mx = max(mx, nd->dec.rbegin()->first-i+a);
int m = (a+b)/2;
if(i <= m) nd = nd->l, b = m;
else nd = nd->r, a = m+1;
}
return mx;
}
};
const int L = 1e8+5;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k, q; cin >> n >> k >> q;
vector<tuple<int, int, int, int>> queries;
for(int i = 0; i < n; i++){
int x, t, a, b; cin >> x >> t >> a >> b; t--;
queries.push_back({a, 0, x, t});
queries.push_back({b, 2, x, t});
}
for(int i = 0; i < q; i++){
int l, y; cin >> l >> y;
queries.push_back({y, 1, l, i});
}
sort(queries.begin(), queries.end());
vector<set<int>> stores(k);
vector<map<int, int>> cnt(k);
sparse_segtree S(L);
auto add = [&](int t, int x){
cnt[t][x]++;
if(cnt[t][x] > 1) return;
auto it = stores[t].insert(x).first;
if(stores[t].size() == 1){
S.add(0, x, x, false);
S.add(x+1, L-1, 1, true);
}
else if(it == stores[t].begin()){
S.remove(0, *next(it), *next(it), false);
S.add(0, x, x, false);
int md = (x+*next(it))/2;
if(md > x) S.add(x+1, md, 1, true);
S.add(md+1, *next(it), *next(it)-md-1, false);
}
else if(next(it) == stores[t].end()){
S.remove(*prev(it)+1, L-1, 1, true);
int md = (*prev(it)+x)/2;
if(md > *prev(it)) S.add(*prev(it)+1, md, 1, true);
S.add(md+1, x, x-md-1, false);
S.add(x+1, L-1, 1, true);
}
else{
int md = (*prev(it)+*next(it));
if(md > *prev(it)) S.remove(*prev(it)+1, md, 1, true);
S.remove(md+1, *next(it), *next(it)-md-1, false);
md = (*prev(it)+x)/2;
if(md > *prev(it)) S.add(*prev(it)+1, md, 1, true);
S.add(md+1, x, x-md-1, false);
S.add(x+1, L-1, 1, true);
md = (x+*next(it))/2;
if(md > x) S.add(x+1, md, 1, true);
S.add(md+1, *next(it), *next(it)-md-1, false);
}
};
auto remove = [&](int t, int x){
cnt[t][x]--;
if(cnt[t][x] > 0) return;
auto it = stores[t].find(x);
if(stores[t].size() == 1){
S.remove(0, x, x, false);
S.remove(x+1, L-1, 1, true);
}
else if(it == stores[t].begin()){
S.add(0, *next(it), *next(it), false);
S.remove(0, x, x, false);
int md = (x+*next(it))/2;
if(md > x) S.remove(x+1, md, 1, true);
S.remove(md+1, *next(it), *next(it)-md-1, false);
}
else if(next(it) == stores[t].end()){
S.add(*prev(it)+1, L-1, 1, true);
int md = (*prev(it)+x)/2;
if(md > *prev(it)) S.remove(*prev(it)+1, md, 1, true);
S.remove(md+1, x, x-md-1, false);
S.remove(x+1, L-1, 1, true);
}
else{
int md = (*prev(it)+*next(it));
if(md > *prev(it)) S.add(*prev(it)+1, md, 1, true);
S.add(md+1, *next(it), *next(it)-md-1, false);
md = (*prev(it)+x)/2;
if(md > *prev(it)) S.remove(*prev(it)+1, md, 1, true);
S.remove(md+1, x, x-md-1, false);
S.remove(x+1, L-1, 1, true);
md = (x+*next(it))/2;
if(md > x) S.remove(x+1, md, 1, true);
S.remove(md+1, *next(it), *next(it)-md-1, false);
}
stores[t].erase(it);
};
vector<int> cnt_t(k, 0);
int nonzero = 0;
vector<int> ans(q);
for(auto [_, type, x, i]: queries){
if(type == 0){
cnt_t[i]++;
if(cnt_t[i] == 1) nonzero++;
add(i, x);
}
else if(type == 2){
cnt_t[i]--;
if(cnt_t[i] == 0) nonzero--;
remove(i, x);
}
else{
if(nonzero < k) ans[i] = -1;
else ans[i] = S.get(x);
}
}
for(int x: ans) cout << x << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
113 ms |
548300 KB |
Output is correct |
| 2 |
Correct |
114 ms |
548436 KB |
Output is correct |
| 3 |
Correct |
114 ms |
548180 KB |
Output is correct |
| 4 |
Incorrect |
110 ms |
548432 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
113 ms |
548300 KB |
Output is correct |
| 2 |
Correct |
114 ms |
548436 KB |
Output is correct |
| 3 |
Correct |
114 ms |
548180 KB |
Output is correct |
| 4 |
Incorrect |
110 ms |
548432 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6476 ms |
1048576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5375 ms |
1048576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
113 ms |
548300 KB |
Output is correct |
| 2 |
Correct |
114 ms |
548436 KB |
Output is correct |
| 3 |
Correct |
114 ms |
548180 KB |
Output is correct |
| 4 |
Incorrect |
110 ms |
548432 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
113 ms |
548300 KB |
Output is correct |
| 2 |
Correct |
114 ms |
548436 KB |
Output is correct |
| 3 |
Correct |
114 ms |
548180 KB |
Output is correct |
| 4 |
Incorrect |
110 ms |
548432 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
