#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define arr3 array<int, 3>
const int inf = 1e8;
const int inff = inf + 1;
const int N = 3e5 + 2;
const int NN = 1e7;
struct IT{
struct node{
int m1, m2, m3, m4, i, l, r;
node(){
l = r = 0;
m1 = m3 = inff; m2 = m4 = 0;
}
};
multiset<int> s1[N], s2[N], s3[N], s4[N];
node all[NN];
int cc, cc1;
void init(){
cc = 1; cc1 = 0;
}
int nw(int tl, int tr){
cc++;
if (tl == tr){
cc1++;
all[cc].i = cc1;
}
return cc;
}
void recalc(int v){
all[v].m1 = all[v].m3 = inff; all[v].m2 = all[v].m4 = 0;
if (all[v].l){
all[v].m1 = min(all[v].m1, all[all[v].l].m1);
all[v].m2 = max(all[v].m2, all[all[v].l].m2);
all[v].m3 = min(all[v].m3, all[all[v].l].m3);
all[v].m4 = max(all[v].m4, all[all[v].l].m4);
}
if (all[v].r){
all[v].m1 = min(all[v].m1, all[all[v].r].m1);
all[v].m2 = max(all[v].m2, all[all[v].r].m2);
all[v].m3 = min(all[v].m3, all[all[v].r].m3);
all[v].m4 = max(all[v].m4, all[all[v].r].m4);
}
}
void add1(int v, int tl, int tr, int p, int x, bool t){
if (tl == tr){
if (t){
s4[all[v].i].insert(x);
all[v].m4 = max(all[v].m4, x);
}
else{
s3[all[v].i].insert(x);
all[v].m3 = min(all[v].m3, x);
}
return;
}
int tm = (tl + tr) / 2;
if (p <= tm){
if (!all[v].l) all[v].l = nw(tl, tm);
add1(all[v].l, tl, tm, p, x, t);
}
else {
if (!all[v].r) all[v].r = nw(tm + 1, tr);
add1(all[v].r, tm + 1, tr, p, x, t);
}
recalc(v);
}
void add2(int v, int tl, int tr, int p, int x, bool t){
if (tl == tr){
if (t){
s2[all[v].i].insert(x);
all[v].m2 = max(all[v].m2, x);
}
else{
s1[all[v].i].insert(x);
all[v].m1 = min(all[v].m1, x);
}
return;
}
int tm = (tl + tr) / 2;
if (p <= tm){
if (!all[v].l) all[v].l = nw(tl, tm);
add2(all[v].l, tl, tm, p, x, t);
}
else {
if (!all[v].r) all[v].r = nw(tm + 1, tr);
add2(all[v].r, tm + 1, tr, p, x, t);
}
recalc(v);
}
void add(int l, int r){
if (l == 1){
add1(1, 1, inf, r, r + 1, 1);
return;
}
if (r == inf){
add1(1, 1, inf, l, l - 1, 0);
return;
}
int m = (l + r) / 2;
if (l <= m) add2(1, 1, inf, m, l - 1, 0);
if (m < r) add2(1, 1, inf, m + 1, r + 1, 1);
}
void rem1(int v, int tl, int tr, int p, int x, bool t){
if (tl == tr){
if (t){
s4[all[v].i].erase(s4[all[v].i].find(x));
all[v].m4 = s4[all[v].i].empty() ? 0 : *prev(s4[all[v].i].end());
}
else{
s4[all[v].i].erase(s3[all[v].i].find(x));
all[v].m3 = s3[all[v].i].empty() ? inff : *s3[all[v].i].begin();
}
return;
}
int tm = (tl + tr) / 2;
if (p <= tm){
rem1(all[v].l, tl, tm, p, x, t);
}
else {
rem1(all[v].r, tm + 1, tr, p, x, t);
}
recalc(v);
}
void rem2(int v, int tl, int tr, int p, int x, bool t){
if (tl == tr){
if (t){
s2[all[v].i].erase(s2[all[v].i].find(x));
all[v].m2 = s2[all[v].i].empty() ? 0 : *prev(s2[all[v].i].end());
}
else{
s1[all[v].i].erase(s1[all[v].i].find(x));
all[v].m1 = s1[all[v].i].empty() ? inff : *s1[all[v].i].begin();
}
return;
}
int tm = (tl + tr) / 2;
if (p <= tm){
rem2(all[v].l, tl, tm, p, x, t);
}
else {
rem2(all[v].r, tm + 1, tr, p, x, t);
}
recalc(v);
}
void rem(int l, int r){
if (l == 1){
rem1(1, 1, inf, r, r + 1, 1);
return;
}
if (r == inf){
rem1(1, 1, inf, l, l - 1, 0);
return;
}
int m = (l + r) / 2;
if (l <= m) rem2(1, 1, inf, m, l - 1, 0);
if (m < r) rem2(1, 1, inf, m + 1, r + 1, 1);
}
int get1(int v, int tl, int tr, int l, int r, bool t){
if (l > tr || r < tl) return inff * !t;
if (l <= tl && tr <= r) return (t) ? all[v].m2 : all[v].m1;
int tm = (tl + tr) / 2, out = inff * !t;
if (all[v].l){
if (t){
out = max(out, get1(all[v].l, tl, tm, l, r, t));
}
else {
out = min(out, get1(all[v].l, tl, tm, l, r, t));
}
}
if (all[v].r){
if (t){
out = max(out, get1(all[v].r, tm + 1, tr, l, r, t));
}
else {
out = min(out, get1(all[v].r, tm + 1, tr, l, r, t));
}
}
return out;
}
int get2(int v, int tl, int tr, int l, int r, bool t){
if (l > tr || r < tl) return inff * !t;
if (l <= tl && tr <= r) return (t) ? all[v].m4 : all[v].m3;
int tm = (tl + tr) / 2, out = inff * !t;
if (all[v].l){
if (t){
out = max(out, get2(all[v].l, tl, tm, l, r, t));
}
else {
out = min(out, get2(all[v].l, tl, tm, l, r, t));
}
}
if (all[v].r){
if (t){
out = max(out, get2(all[v].r, tm + 1, tr, l, r, t));
}
else {
out = min(out, get2(all[v].r, tm + 1, tr, l, r, t));
}
}
return out;
}
pii get(int x){
return {min(get1(1, 1, inf, x, inf, 0), get2(1, 1, inf, 1, x, 0)), max(get1(1, 1, inf, 1, x, 1), get2(1, 1, inf, x, inf, 1))};
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k, q; cin>>n>>k>>q;
vector<int> x(n + 1), t(n + 1), a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++){
cin>>x[i]>>t[i]>>a[i]>>b[i];
}
vector<int> xq(q + 1), yq(q + 1);
for (int i = 1; i <= q; i++){
cin>>xq[i]>>yq[i];
}
vector<arr3> mp;
for (int i = 1; i <= n; i++){
mp.pb({a[i], 1, i});
if (b[i] < inf) mp.pb({b[i] + 1, 2, i});
}
for (int i = 1; i <= q; i++){
mp.pb({yq[i], i + 2, xq[i]});
}
auto cmp = [&](arr3 x, arr3 y){
if (x[0] == y[0]){
return x[1] < y[1];
}
return x[0] < y[0];
};
sort(mp.begin(), mp.end(), cmp);
vector<int> out(q + 1), cnt(k + 1);
multiset<int> st[k + 1];
int df = 0, l, r;
IT T; T.init();
for (auto [X, tt, i]: mp){
if (tt == 1){
df += !cnt[t[i]];
cnt[t[i]]++;
if (cnt[t[i]] == 1){
if (1 < x[i]) T.add(1, x[i] - 1);
if (x[i] < inf) T.add(x[i] + 1, inf);
st[t[i]].insert(x[i]);
continue;
}
if (st[t[i]].find(x[i]) != st[t[i]].end()){
st[t[i]].insert(x[i]);
continue;
}
auto it = st[t[i]].upper_bound(x[i]);
if (it == st[t[i]].end()) r = inf;
else r = (*it) - 1;
if (it == st[t[i]].begin()) l = 1;
else l = *prev(it) + 1;
if (l <= r) T.rem(l, r);
if (l < x[i]) T.add(l, x[i] - 1);
if (x[i] < r) T.add(x[i] + 1, r);
st[t[i]].insert(x[i]);
}
else if (tt == 2){
cnt[t[i]]--;
df -= !cnt[t[i]];
if (st[t[i]].count(x[i]) > 1){
st[t[i]].erase(st[t[i]].find(x[i]));
continue;
}
auto it = st[t[i]].find(x[i]);
if (it == st[t[i]].begin()) l = 1;
else l = *prev(it) + 1;
if (it == prev(st[t[i]].end())) r = inf;
else r = *next(it) - 1;
if (l < x[i]) T.rem(l, x[i] - 1);
if (x[i] < r) T.rem(x[i] + 1, r);
if (cnt[t[i]]) T.add(l, r);
st[t[i]].erase(it);
}
else {
int ii = tt - 2;
if (df < k){
out[ii] = -1;
continue;
}
auto [l, r] = T.get(i);
if (l != inff) out[ii] = max(out[ii], i - l);
if (r != 0) out[ii] = max(out[ii], r - i);
}
}
for (int i = 1; i <= q; i++){
cout<<out[i]<<"\n";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
718 ms |
670280 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
718 ms |
670280 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
887 ms |
709796 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
871 ms |
712612 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
718 ms |
670280 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
718 ms |
670280 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
