#include "bits/stdc++.h"
using namespace std;
namespace NLOGsq{
#define ar array
#define pq priority_queue
const int N = 3e5 + 5;
const int M = N * 30;
const int MX = 1e8 + 5;
struct ST{
pq<int> tree[M][2], bad[M][2];
int f[M][2], last;
ST(){
last = 0;
}
void make(int x){
if(!f[x][0]) f[x][0] = ++last;
if(!f[x][1]) f[x][1] = ++last;
//~ assert(last < M);
}
void add(int l, int r, int s, int t, int lx = 0, int rx = MX, int x = 0){
if(lx > r || rx < l) return;
if(lx >= l && rx <= r){
if(t == 1){
tree[x][0].push(s + (lx - l));
} else {
tree[x][1].push(s - (lx - l));
} return;
} int m = (lx + rx) >> 1;
make(x);
add(l, r, s, t, lx, m, f[x][0]), add(l, r, s, t, m+1, rx, f[x][1]);
}
void bal(pq<int>& a, pq<int>& b){
while(!a.empty() && !b.empty() && a.top() == b.top()){
a.pop();
b.pop();
}
}
void del(int l, int r, int s, int t, int lx = 0, int rx = MX, int x = 0){
if(lx > r || rx < l) return;
if(lx >= l && rx <= r){
if(t == 1){
bad[x][0].push(s + (lx - l));
} else {
bad[x][1].push(s - (lx - l));
} return;
} int m = (lx + rx) >> 1;
make(x);
del(l, r, s, t, lx, m, f[x][0]), del(l, r, s, t, m+1, rx, f[x][1]);
}
int get(int i, int lx = 0, int rx = MX, int x = 0){
int res = 0;
bal(tree[x][0], bad[x][0]);
bal(tree[x][1], bad[x][1]);
if(!tree[x][0].empty()) res = max(res, tree[x][0].top() + (i - lx));
if(!tree[x][1].empty()) res = max(res, tree[x][1].top() - (i - lx));
if(lx == rx) return res;
int m = (lx + rx) >> 1;
if(i <= m) return max((f[x][0] ? get(i, lx, m, f[x][0]) : 0), res);
else return max((f[x][1] ? get(i, m+1, rx, f[x][1]) : 0), res);
}
}tree;
/*
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
2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7
1 1 1
100000000 1 1 1
1 1
*/
int x[N], t[N], a[N], b[N], l[N], y[N];
multiset<int> ss[N];
void solve(int n, int k, int q){ // assert(false);
for(int i=0;i<n;i++){
cin>>x[i]>>t[i]>>a[i]>>b[i];
--t[i];
}
auto add = [&](int l, int r){
if(l == r) return;
int m = (l + r) >> 1;
tree.add(l, m, 0, 1);
tree.add(m + 1, r, r - m - 1, -1);
}; auto inc = [&](int x) { tree.add(x, MX, 0, 1); };
auto dec = [&](int x) { tree.add(0, x, x, -1); };
auto dadd = [&](int l, int r){
if(l == r) return;
int m = (l + r) >> 1;
tree.del(l, m, 0, 1);
tree.del(m + 1, r, r - m - 1, -1);
}; auto dinc = [&](int x) { tree.del(x, MX, 0, 1); };
auto ddec = [&](int x) { tree.del(0, x, x, -1); };
//~ bool is = 1;
//~ for(int i=0;i<k;i++){
//~ if(stor[i].empty()) { is = 0; break; }
//~ sort(stor[i].begin(), stor[i].end(), [&](int i, int j){
//~ return (x[i] < x[j]);
//~ });
//~ for(int j=1;j<(int)stor[i].size();j++){
//~ add(x[stor[i][j-1]], x[stor[i][j]]);
//~ }
//~ dec(x[stor[i][0]]);
//~ inc(x[stor[i].back()]);
//~ }
vector<int> in(n); iota(in.begin(), in.end(), 0);
vector<int> out(n); iota(out.begin(), out.end(), 0);
sort(in.begin(), in.end(), [&](int i, int j){
return (a[i] < a[j]);
});
sort(out.begin(), out.end(), [&](int i, int j){
return (b[i] < b[j]);
});
vector<int> p(q);
for(int i=0;i<q;i++){ p[i] = i;
cin>>l[i]>>y[i];
}
sort(p.begin(), p.end(), [&](int i, int j){
return (y[i] < y[j]);
});
int I = 0, O = 0, c = k;
auto NEW = [&](int i){
auto it = ss[t[i]].upper_bound(x[i]);
if(ss[t[i]].empty()) c--;
if(it == ss[t[i]].end()){
if(it != ss[t[i]].begin()){
it--;
dinc(*it);
add(*it, x[i]);
inc(x[i]);
} else {
inc(x[i]);
dec(x[i]);
}
} else {
if(it == ss[t[i]].begin()){
ddec(*it);
add(x[i], *it);
dec(x[i]);
} else {
auto R = it; it--;
dadd(*it, *R);
add(*it, x[i]);
add(x[i], *R);
}
}
ss[t[i]].insert(x[i]);
};
auto DEL = [&](int i){
ss[t[i]].erase(ss[t[i]].find(x[i]));
if(ss[t[i]].empty()) c++;
auto it = ss[t[i]].upper_bound(x[i]);
if(it == ss[t[i]].end()){
if(it == ss[t[i]].begin()){
dinc(x[i]);
ddec(x[i]);
} else {
it--;
dadd(*it, x[i]);
dinc(x[i]);
inc(*it);
}
} else {
if(it == ss[t[i]].begin()){
dadd(x[i], *it);
ddec(x[i]);
dec(*it);
} else {
auto R = it; it--;
dadd(*it, x[i]);
dadd(x[i], *R);
add(*it, *R);
}
}
};
vector<int> res(q);
for(auto i : p){
while(I < n && a[in[I]] <= y[i]){
NEW(in[I]);
I++;
}
while(O < n && b[out[O]] < y[i]){
DEL(out[O]);
O++;
}
if(!c) res[i] = tree.get(l[i]);
else res[i] = -1;
}
for(int i=0;i<q;i++) cout<<res[i]<<"\n";
}
};
namespace temp{
const int N = 3e5 + 5;
const int M = N * 30;
const int MX = 1e8 + 5;
struct ST{
int tree[M][2], f[M][2];
int last;
ST(){
memset(tree, -1, sizeof tree);
last = 0;
}
void make(int x){
if(!f[x][0]) f[x][0] = ++last;
if(!f[x][1]) f[x][1] = ++last;
}
void umax(int l, int r, int s, int t, int lx = 0, int rx = MX, int x = 0){
if(lx > r || rx < l) return;
if(lx >= l && rx <= r){
if(t == 1) tree[x][0] = max(tree[x][0], s + (lx - l));
else tree[x][1] = max(tree[x][1], s - (lx - l));
return;
} int m = (lx + rx) >> 1;
make(x);
umax(l, r, s, t, lx, m, f[x][0]);
umax(l, r, s, t, m+1, rx, f[x][1]);
}
int get(int i, int lx = 0, int rx = MX, int x = 0){
int res = 0;
if(~tree[x][0]) res = max(res, tree[x][0] + (i - lx));
if(~tree[x][1]) res = max(res, tree[x][1] - (i - lx));
if(lx == rx) return res;
int m = (lx + rx) >> 1;
if(i <= m) return max((f[x][0] ? get(i, lx, m, f[x][0]) : 0), res);
else return max((f[x][1] ? get(i, m+1, rx, f[x][1]) : 0), res);
}
}tree;
int x[N], t[N], a[N], b[N], l[N], y[N];
multiset<int> ss[N];
vector<int> stor[N];
void solve(int n, int k, int q){
for(int i=0;i<n;i++){
cin>>x[i]>>t[i]>>a[i]>>b[i];
--t[i];
stor[t[i]].push_back(i);
}
auto add = [&](int l, int r){
if(l == r) return;
int m = (l + r) >> 1;
tree.umax(l, m, 0, 1);
tree.umax(m + 1, r, r - m - 1, -1);
}; auto inc = [&](int x) { tree.umax(x, MX, 0, 1); };
auto dec = [&](int x) { tree.umax(0, x, x, -1); };
vector<int> out(n); iota(out.begin(), out.end(), 0);
sort(out.begin(), out.end(), [&](int i, int j){
return (b[i] < b[j]);
});
vector<int> p(q);
for(int i=0;i<q;i++){ p[i] = i;
cin>>l[i]>>y[i];
}
sort(p.begin(), p.end(), [&](int i, int j){
return (y[i] < y[j]);
});
int O = 0, c = 0;
for(int i=0;i<k;i++){
if(stor[i].empty()) { c++; break; }
sort(stor[i].begin(), stor[i].end(), [&](int i, int j){
return (x[i] < x[j]);
});
for(int j=1;j<(int)stor[i].size();j++){
add(x[stor[i][j-1]], x[stor[i][j]]);
}
inc(x[stor[i].back()]);
dec(x[stor[i][0]]);
}
auto DEL = [&](int i){
ss[t[i]].erase(ss[t[i]].find(x[i]));
if(ss[t[i]].empty()) c++;
auto it = ss[t[i]].upper_bound(x[i]);
if(it == ss[t[i]].end()){
if(it != ss[t[i]].begin()){
it--;
inc(*it);
}
} else {
if(it == ss[t[i]].begin()){
dec(*it);
} else {
auto R = it; it--;
add(*it, *R);
}
}
};
vector<int> res(q);
for(auto i : p){
while(O < n && b[out[O]] < y[i]){
DEL(out[O]);
O++;
}
if(!c) res[i] = tree.get(l[i]);
else res[i] = -1;
}
for(int i=0;i<q;i++) cout<<res[i]<<"\n";
}
};
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, k, q; cin>>n>>k>>q;
if(n <= 60000 && q <= 60000){
NLOGsq::solve(n, k, q);
} else {
temp::solve(n, k, q);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
476 ms |
1048664 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
476 ms |
1048664 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
373 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
383 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
476 ms |
1048664 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
476 ms |
1048664 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
