#include <iostream>
using namespace std;
#include <vector>
#define vi vector<int>
#define ll long long
#include <algorithm>
#include <set>
#include <string>
#include <bitset>
#include <cmath>
#include <math.h>
#define pll pair<ll,ll>
#define vll vector<ll>
#define pi pair<int,int>
#include <map>
#include <queue>
#define pd pair<double,double>
const int siz = 3e5 + 2;
multiset<int> col[siz];
int K;
struct node {
int l, r, mid, maxi;
bool p=0;
multiset<int> s;
node* sl = NULL;
node *sr = NULL;
node(int li, int ri) {
l = li, r = ri, mid = (l + r) / 2, maxi = 0;
if (l == 0) {
maxi = 3e8 + 1;
if (r == 0) {
for (int i = 0; i < K; i++)s.insert(3e8 + 1);
}
else open();
}
}
void open() {
if (sl == NULL && (l < r)) {
p = 1;
sl = new node(l, mid);
sr = new node(mid + 1, r);
}
}
int query(int a, int b) {
if (a > r || b < l || maxi==0)return 0;
if (a <= l && b >= r)return maxi;
if (p)return max(sl->query(a, b), sr->query(a, b));
return 0;
}
void update(int v, int x, bool f) {
if (l == r) {
if (f)s.insert(v);
else s.erase(s.find(v));
if (s.size())maxi = *(--s.end());
else maxi = 0;
}
else {
if (sl == NULL)open();
if (x <= mid) {
sl->update(v, x, f);
}
else {
sr->update(v, x, f);
}
maxi = max(sl->maxi, sr->maxi);
}
}
};
map<pi, int> sum;
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, k, q;
cin >> n >> k >> q;
vector<vi> ev;
K = k;
for (int i = 0; i < n; i++) {
int x, t, a, b;
cin >> x >> t >> a >> b;
x++;
ev.push_back({ a,1,x,t });
ev.push_back({b+1,0,x,t });
}
for (int i = 0; i < siz; i++) {
col[i].insert(0);
col[i].insert(3e8 + 1);
}
for (int i = 0; i < q; i++) {
int l, y;
cin >> l >> y;
l++;
ev.push_back({ y,l,i });
}
sort(ev.begin(), ev.end());
node* seg = new node(0, 3e8 + 3);
vi ans(q);
for (vi v : ev) {
if (v.size() == 3) {
int l = v[1];
int a = 0, b = 1e8 + 3;
while (a < b) {
int mid = (a + b) / 2;
int ans = seg->query(0, max(l - mid - 1, 0));
if (ans <= mid + l) {
b = mid;
}
else {
a = mid+1;
}
}
if (b == 1e8 + 3)ans[v[2]] = -1;
else ans[v[2]] = b;
}
else {
int x = v[2], t = v[3];
//if (v[1])sum[{x, t}]++;
//else sum[{x,t}]--;
//if (v[1] == sum[{x,t}]) {
auto it = col[t].lower_bound(x);
auto it1 = it, it2 = it;
it1--; if (v[1] == 0)it2++;
if (v[1] == 0)col[t].erase(x);
else col[t].insert(x);
seg->update(*it2, x, v[1]);
seg->update(*it2, *it1, !v[1]);
seg->update(x, *it1, v[1]);
//}
}
}
for (int i = 0; i < q; i++)cout << ans[i] << "\n";
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
64 ms |
86096 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
64 ms |
86096 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3494 ms |
608516 KB |
Output is correct |
| 2 |
Execution timed out |
5068 ms |
603740 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5087 ms |
604420 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
64 ms |
86096 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
64 ms |
86096 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
