#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 1000005
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
int x[N], ans[N], y[N], l[N], t[N], a[N], b[N];
int n, k, q;
vector<int> tmp;
vector<pair<int, int> > sh[N];
multiset<pair<int, int> > in;
vector<pair<pair<int, int>, pair<int, int> > > lol;
int seg[N];
void update(int id, int l, int r, int L, int R, int v){
if(l >= L && r <= R){
seg[id] = max(seg[id], v);
return;
}
if(l > R || r < L) return;
int m = (l + r) >> 1;
update(id << 1, l, m, L, R, v);
update(id << 1 | 1, m + 1, r, L, R, v);
}
int query(int id, int l, int r, int x){
if(x < l || x > r) return 0;
if(l == r) return seg[id];
int m = (l + r) >> 1;
return max(seg[id], max(query(id << 1, l, m, x), query(id << 1 | 1, m + 1, r, x)));
}
void solve(){
lol.clear();
memset(seg, 0, sizeof seg);
for(int i = 1; i <= k; ++i){
in.clear();
in.insert({INF, 1});
in.insert({-INF, 1});
for(auto& x : sh[i]){
if(x.ss > 0){
auto r = in.insert({x.ss, x.ff});
auto l = r++;
auto it = l--;
lol.push_back({{(r -> ff + l -> ff) / 2, r -> ff}, {r -> ss, x.ff - 1}});
in.insert({r -> ff, x.ff});
in.erase(r);
} else {
auto r = in.lower_bound({x.ss, 0});
auto l = r++;
auto it = l--;
lol.push_back({{(it -> ff + l -> ff) / 2, it -> ff}, {it -> ss, x.ff - 1}});
lol.push_back({{(it -> ff + r -> ff) / 2, r -> ff}, {r -> ss, x.ff - 1}});
in.insert({r -> ff, x.ff});
in.erase(it);
in.erase(r);
}
}
auto r = in.begin();
auto l = r++;
lol.push_back({{(r -> ff + l -> ff) / 2, r -> ff}, {r -> ss, tmp.size()}});
}
for(int i = 1; i <= q; ++i)
lol.push_back({{l[i], 1'000'000'000}, {i, y[i]}});
sort(lol.begin(), lol.end());
for(auto& x : lol){
if(x.ff.ss != 1'000'000'000){
if(x.ss.ff <= x.ss.ss && x.ff.ss > 0){
update(1, 1, 300'005, x.ss.ff, x.ss.ss, x.ff.ss);
}
}
else
ans[x.ss.ff] = max(ans[x.ss.ff], query(1, 1, 300'005, x.ss.ss) - x.ff.ff);
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k>>q;
for(int i = 1; i <= n; ++i)
cin>>x[i]>>t[i]>>a[i]>>b[i];
for(int i = 1; i <= q; ++i){
cin>>l[i]>>y[i];
l[i] <<= 1;
tmp.push_back(y[i]);
}
sort(tmp.begin(), tmp.end());
tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin());
for(int i = 1; i <= q; ++i)
y[i] = upper_bound(tmp.begin(), tmp.end(), y[i]) - tmp.begin();
for(int i = 1; i <= n; ++i){
a[i] = lower_bound(tmp.begin(), tmp.end(), a[i]) - tmp.begin() + 1;
b[i] = lower_bound(tmp.begin(), tmp.end(), b[i]) - tmp.begin() + 1;
if(a[i] < b[i]){
x[i] <<= 1;
sh[t[i]].push_back({a[i], x[i]});
sh[t[i]].push_back({b[i], -x[i]});
}
}
for(int i = 1; i <= k; ++i)
sort(sh[i].begin(), sh[i].end());
solve();
for(int i = 1; i <= q; ++i)
l[i] = 200'000'002 - l[i];
for(int i = 1; i <= k; ++i)
for(auto& x : sh[i])
if(x.ss > 0)
x.ss = 200'000'002 - x.ss;
else
x.ss = -200'000'002 - x.ss;
solve();
for(int i = 1; i <= q; ++i){
if(ans[i] > 400'000'002)
cout<<"-1\n";
else
cout<<ans[i] / 2<<'\n';
}
}
Compilation message
new_home.cpp: In function 'void solve()':
new_home.cpp:49:22: warning: variable 'it' set but not used [-Wunused-but-set-variable]
auto it = l--;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
27776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
27776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1130 ms |
90444 KB |
Output is correct |
| 2 |
Incorrect |
1091 ms |
89296 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
943 ms |
140896 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
27776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
27776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
