#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 = 5e6 + 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{
int t[M], l[M], r[M];
int cur = 0;
segtree(){
t[0] = -infi;
l[0] = -1;
r[0] = -1;
}
void zer(int v, int tl, int tr, int i){
if(tl == tr){
t[v] = -infi;
//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] = ++cur;
t[cur] = -infi;
l[cur] = -1;
r[cur] = -1;
}
zer(l[v], tl, tm, i);
}else{
if(r[v] == -1){
r[v] = ++cur;
t[cur] = -infi;
l[cur] = -1;
r[cur] = -1;
}
zer(r[v], tm + 1, tr, i);
}
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]]);
}
void add(int v, int tl, int tr, int i, int x){
if(tl == tr){
t[v] = max(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] = ++cur;
t[cur] = -infi;
l[cur] = -1;
r[cur] = -1;
}
add(l[v], tl, tm, i, x);
}else{
if(r[v] == -1){
r[v] = ++cur;
t[cur] = -infi;
l[cur] = -1;
r[cur] = -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';
}
void sett(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] = ++cur;
t[cur] = -infi;
l[cur] = -1;
r[cur] = -1;
}
add(l[v], tl, tm, i, x);
}else{
if(r[v] == -1){
r[v] = ++cur;
t[cur] = -infi;
l[cur] = -1;
r[cur] = -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];
map<int, multiset<int>> spl, spr;
segtree lt = segtree(), rt = segtree();
void add(int i, int x1, int x2){
lt.add(0, L, R, i, x1);
rt.add(0, L, R, i, x2);
spl[i].insert(x1);
spr[i].insert(x2);
}
void rem(int i, int x1, int x2){
if(*(--spl[i].end()) == x1){
spl[i].erase(spl[i].find(x1));
if(spl[i].size() > 0){
lt.sett(0, L, R, i, *(--spl[i].end()));
}else{
lt.zer(0, L, R, i);
}
}else{
spl[i].erase(spl[i].find(x1));
}
if(*(--spr[i].end()) == x2){
rt.zer(0, L, R, i);
spr[i].erase(spr[i].find(x2));
if(spr[i].size() > 0)
rt.add(0, L, R, i, *(--spr[i].end()));
}else{
spr[i].erase(spr[i].find(x2));
}
}
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());
int cnt = k;
for(auto ev : evs){
//cout << ev.F.F << ' ' << ev.F.S << ' ' << ev.S.F << ' ' << ev.S.S << '\n';
if(ev.F.S == 1){
int x = ev.S.F, tp = ev.S.S;
if(cr[tp].find(x) != cr[tp].end()){
cr[tp].insert(x);
continue;
}
if(cr[tp].size() == 0){
cr[tp].insert(x);
add(L, x, x - 2 * L);
add(R, 2 * R - x, -x);
cnt--;
continue;
}
int l = -1, r = -1;
auto it = cr[tp].upper_bound(x);
if(it != cr[tp].end()){
add(((*it) + x) / 2, *it, -x);
r = *it;
}else{
add(R, 2 * R - x, -x);
}
it = cr[tp].lower_bound(x);
if(it != cr[tp].begin()){
it--;
add((x + (*it)) / 2, x, -(*it));
l = *it;
}else{
add(L, x, x - 2 * L);
}
if(l != -1 && r != -1){
rem((r + l) / 2, r, -l);
}
if(r == -1 && l != -1){
rem(R, 2 * R - l, -l);
}
if(r != -1 && l == -1){
rem(L, r, r - 2 * L);
}
cr[tp].insert(x);
}else if(ev.F.S == -1){
int x = ev.S.F, tp = ev.S.S;
int l = -1, r = -1;
if(cr[tp].count(x) > 1){
cr[tp].erase(cr[tp].find(x));
continue;
}
auto it = cr[tp].upper_bound(x);
if(it != cr[tp].end()){
r = *it;
rem((r + x) / 2, r, -x);
}else{
rem(R, 2 * R - x, -x);
}
it = cr[tp].lower_bound(x);
if(it != cr[tp].begin()){
it--;
l = (*it);
rem((x + l) / 2, x, -l);
}else{
rem(L, x, x - 2 * L);
}
cr[tp].erase(cr[tp].find(x));
if(l == -1 && r == -1){
cnt++;
}else if(l == -1){
add(L, r, r - 2 * L);
}else if(r == -1){
add(R, 2 * R - l, -l);
}else{
add((r + l) / 2, r, -l);
}
}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);
}
//cout << cnt << '\n';
}
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 |
7 ms |
37200 KB |
Output is correct |
| 2 |
Correct |
6 ms |
37408 KB |
Output is correct |
| 3 |
Correct |
6 ms |
37200 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
37200 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
37200 KB |
Output is correct |
| 2 |
Correct |
6 ms |
37408 KB |
Output is correct |
| 3 |
Correct |
6 ms |
37200 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
37200 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3191 ms |
276964 KB |
Output is correct |
| 2 |
Correct |
1866 ms |
309088 KB |
Output is correct |
| 3 |
Correct |
891 ms |
141188 KB |
Output is correct |
| 4 |
Correct |
2844 ms |
254696 KB |
Output is correct |
| 5 |
Correct |
1894 ms |
314012 KB |
Output is correct |
| 6 |
Correct |
1854 ms |
309916 KB |
Output is correct |
| 7 |
Correct |
863 ms |
141216 KB |
Output is correct |
| 8 |
Correct |
2908 ms |
260628 KB |
Output is correct |
| 9 |
Correct |
3255 ms |
292996 KB |
Output is correct |
| 10 |
Correct |
2111 ms |
310176 KB |
Output is correct |
| 11 |
Correct |
1728 ms |
305528 KB |
Output is correct |
| 12 |
Correct |
1996 ms |
307184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5061 ms |
408120 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
37200 KB |
Output is correct |
| 2 |
Correct |
6 ms |
37408 KB |
Output is correct |
| 3 |
Correct |
6 ms |
37200 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
37200 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
37200 KB |
Output is correct |
| 2 |
Correct |
6 ms |
37408 KB |
Output is correct |
| 3 |
Correct |
6 ms |
37200 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
37200 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
