#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
#define int ll
using ld = long double;
using pii = pair<int, int>;
#define F first
#define S second
const ld PI = 3.1415926535;
const int N = 5e5 + 2;
const int M = 2e6 + 1;
int mod = 998244353;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
int mult(int a, int b) {
return a * 1LL * b % mod;
}
int sum(int a, int b) {
if (a + b < 0)
return a + b + mod;
if (a + b >= mod)
return a + b - mod;
return a + b;
}
ll binpow(ll a, ll n) {
if (n == 0)
return 1;
if (n % 2 == 1) {
return binpow(a, n - 1) * a % mod;
} else {
ll b = binpow(a, n / 2);
return b * b % mod;
}
}
struct segtree{
vector<int> t, l, r;
segtree(){
t.assign(1, -infi);
l.assign(1, -1);
r.assign(1, -1);
}
void add(int v, int tl, int tr, int i, int x){
if(tl == tr){
t[v] = x;
//cout << v << ' ' << l[v] << ' ' << r[v] << ' ' << tl << ' ' << tr << ' ' << t[v] << '\n';
return;
}
int tm = (tl + tr) / 2;
if(i <= tm){
if(l[v] == -1){
l[v] = t.size();
t.push_back(-infi);
l.push_back(-1);
r.push_back(-1);
}
add(l[v], tl, tm, i, x);
}else{
if(r[v] == -1){
r[v] = t.size();
t.push_back(-infi);
l.push_back(-1);
r.push_back(-1);
}
add(r[v], tm + 1, tr, i, x);
}
t[v] = -infi;
if(l[v] != -1)
t[v] = max(t[v], t[l[v]]);
if(r[v] != -1)
t[v] = max(t[v], t[r[v]]);
//cout << v << ' ' << l[v] << ' ' << r[v] << ' ' << tl << ' ' << tr << ' ' << t[v] << '\n';
}
int get(int v, int tl, int tr, int lu, int ru){
if(v == -1)
return -infi;
if(tl > ru || lu > tr)
return -infi;
if(lu <= tl && tr <= ru)
return t[v];
int tm = (tl + tr) / 2;
return max(get(l[v], tl, tm, lu, ru), get(r[v], tm + 1, tr, lu, ru));
}
};
int n, q, k, ans[N], L = 0, R = 2e8;
vector<pair<pii, pii>> evs;
multiset<int> cr[N];
void solve() {
cin >> n >> k >> q;
for(int i = 1; i <= n; i++){
int x, tp, a, b;
cin >> x >> tp >> a >> b;
x *= 2;
evs.push_back({{a, 1}, {x, tp}});
evs.push_back({{b + 1, -1}, {x, tp}});
}
for(int i = 1; i <= q; i++){
int l, y;
cin >> l >> y;
l *= 2;
evs.push_back({{y, 2}, {l, i}});
}
sort(evs.begin(), evs.end());
segtree lt = segtree(), rt = segtree();
int cnt = k;
for(auto ev : evs){
if(ev.F.S == 1){
int x = ev.S.F, tp = ev.S.S;
if(cr[tp].size() == 0){
cr[tp].insert(x);
lt.add(0, L, R, L, x);
lt.add(0, L, R, R, 2 * R - x);
rt.add(0, L, R, R, -x);
rt.add(0, L, R, L, x - 2 * L);
cnt--;
continue;
}
int l = -1, r = -1;
auto it = cr[tp].upper_bound(x);
if(it != cr[tp].end()){
lt.add(0, L, R, ((*it) + x) / 2, *it);
rt.add(0, L, R, ((*it) + x) / 2, -x);
r = *it;
}else{
lt.add(0, L, R, R, 2 * R - x);
rt.add(0, L, R, R, -x);
}
it = cr[tp].lower_bound(x);
if(it != cr[tp].begin()){
it--;
lt.add(0, L, R, (x + (*it)) / 2, x);
rt.add(0, L, R, (x + (*it)) / 2, -(*it));
l = *it;
}else{
lt.add(0, L, R, L, x);
rt.add(0, L, R, L, x - 2 * L);
}
if(l != -1 && r != -1){
lt.add(0, L, R, (r + l) / 2, -infi);
rt.add(0, L, R, (r + l) / 2, -infi);
}
cr[tp].insert(x);
}else if(ev.F.S == -1){
int x = ev.S.F, tp = ev.S.S;
int l = -1, r = -1;
auto it = cr[tp].upper_bound(x);
if(it != cr[tp].end()){
r = *it;
lt.add(0, L, R, (r + x) / 2, -infi);
rt.add(0, L, R, (r + x) / 2, -infi);
}else{
lt.add(0, L, R, R, -infi);
rt.add(0, L, R, R, -infi);
}
it = cr[tp].lower_bound(x);
if(it != cr[tp].begin()){
it--;
l = (*it);
lt.add(0, L, R, (x + l) / 2, -infi);
rt.add(0, L, R, (x + l) / 2, -infi);
}else{
lt.add(0, L, R, L, -infi);
rt.add(0, L, R, L, -infi);
}
if(l == -1 && r == -1){
if(cr[tp].size() == 1){
cnt++;
lt.add(0, L, R, L, -infi);
lt.add(0, L, R, R, -infi);
rt.add(0, L, R, L, -infi);
rt.add(0, L, R, R, -infi);
}else{
lt.add(0, L, R, L, x);
lt.add(0, L, R, R, 2 * R - x);
rt.add(0, L, R, R, -x);
rt.add(0, L, R, L, x - 2 * L);
}
}else if(l == -1){
lt.add(0, L, R, L, r);
rt.add(0, L, R, L, r - 2 * L);
}else if(r == -1){
lt.add(0, L, R, R, 2 * R - l);
rt.add(0, L, R, R, -l);
}else{
lt.add(0, L, R, (r + l) / 2, r);
rt.add(0, L, R, (r + l) / 2, -l);
}
cr[tp].erase(cr[tp].find(x));
}else{
int x = ev.S.F, i = ev.S.S;
int ret = max(lt.get(0, L, R, L, x) - x, rt.get(0, L, R, x, R) + x);
if(cnt != 0)
ans[i] = -1;
else
ans[i] = (ret < 0 ? -1 : ret / 2);
}
}
for(int i = 1; i <=q; i++)
cout << ans[i] << ' ';
cout << '\n';
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25168 KB |
Output is correct |
| 2 |
Correct |
5 ms |
25168 KB |
Output is correct |
| 3 |
Correct |
5 ms |
25168 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
25252 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25168 KB |
Output is correct |
| 2 |
Correct |
5 ms |
25168 KB |
Output is correct |
| 3 |
Correct |
5 ms |
25168 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
25252 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2267 ms |
292788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4316 ms |
385572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25168 KB |
Output is correct |
| 2 |
Correct |
5 ms |
25168 KB |
Output is correct |
| 3 |
Correct |
5 ms |
25168 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
25252 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
25168 KB |
Output is correct |
| 2 |
Correct |
5 ms |
25168 KB |
Output is correct |
| 3 |
Correct |
5 ms |
25168 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
25252 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
