#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10, inf=1e9;
vector<pair<pair<int, int>, pair<int, int>>> vq[N];
int ans[N];
vector<int> vpos, vtime;
struct SegmentTree1{
int n;
vector<int> t;
void init(int _n){
n=_n;
t.assign(4*n+1, -inf);
}
void update(int k, int l, int r, int pos, int val){
if (r<pos || pos<l) return;
if (l==r){
t[k]=val;
return;
}
int mid=(l+r)>>1;
update(k<<1, l, mid, pos, val);
update(k<<1|1, mid+1, r, pos, val);
t[k]=max(t[k<<1], t[k<<1|1]);
}
int get(int k, int l, int r, int L, int R){
if (r<L || R<l) return -inf;
if (L<=l && r<=R) return t[k];
int mid=(l+r)>>1;
return max(get(k<<1, l, mid, L, R), get(k<<1|1, mid+1, r, L, R));
}
} stl, str;
struct SegmentTree2{
int n;
vector<pair<int, pair<int, int>>> t[N*4];
void init(int _n){
n=_n;
}
void update(int k, int l, int r, int L, int R, pair<int, pair<int, int>> val){
if (r<L || R<l) return;
if (L<=l && r<=R){
t[k].push_back(val);
return;
}
int mid=(l+r)>>1;
update(k<<1, l, mid, L, R, val);
update(k<<1|1, mid+1, r, L, R, val);
}
void dfs(int k, int l, int r){
for (auto &i:t[k]){
// cout << "update l " << i.first << ' ' << i.second.first << ' ' << i.second.second << endl;
// cout << "update r " << i.first << ' ' << i.second.first << ' ' << i.second.second << endl;
stl.update(1, 1, stl.n, i.first, i.second.first+i.second.second);
str.update(1, 1, str.n, i.first, i.second.second-i.second.first);
}
if (l==r){
for (auto &i:vq[l]){
ans[i.second.first]=max(stl.get(1, 1, stl.n, 1, i.first.first)-i.second.second, str.get(1, 1, str.n, i.first.second, str.n)+i.second.second)/2;
}
}else{
int mid=(l+r)>>1;
dfs(k<<1, l, mid);
dfs(k<<1|1, mid+1, r);
}
for (auto &i:t[k]){
stl.update(1, 1, stl.n, i.first, 0);
str.update(1, 1, str.n, i.first, 0);
}
}
} st;
int n, q, k;
vector<pair<int, int>> v[N];
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k >> q;
vtime.push_back(-inf*2); vpos.push_back(-inf*2);
vector<pair<int, pair<int, int>>> check;
map<pair<int, int>, vector<pair<int, int>>> mp;
for (int i=1; i<=n; ++i){
int x, t, l, r;
cin >> x >> t >> l >> r; x*=2;
mp[{x, t}].emplace_back(l, r);
}
for (auto &i:mp){
sort(i.second.begin(), i.second.end());
vector<pair<int, int>> vv;
for (auto &j:i.second){
if (vv.size() && vv.back().second+1>=j.first) vv.back().second=max(vv.back().second, j.second);
else vv.push_back(j);
}
i.second.swap(vv);
}
for (auto &i:mp){
int x=i.first.first, t=i.first.second;
for (auto &j:i.second){
int l=j.first, r=j.second;
v[t].emplace_back(l, x);
v[t].emplace_back(r+1, -x);
check.push_back({l, {1, t}});
check.push_back({r+1, {-1, t}});
}
}
vector<vector<int>> events;
for (int i=1; i<=k; ++i){
set<int> st;
map<int, int> mp;
sort(v[i].begin(), v[i].end());
for (auto &j:v[i]){
int pos=abs(j.second), t=j.first;
auto it=st.lower_bound(pos);
if (j.second>0){
if (st.size()){
int x=0, y=0;
if (it==st.begin()) x=-*it, y=*it*2;
else if (it==st.end()) x=inf+*prev(it), y=inf;
else x=(*it+*prev(it))>>1, y=(*it-*prev(it))>>1;
events.push_back({mp[x], t-1, x, y});
mp.erase(x);
}
{
int x=0;
if (it==st.begin()) x=-pos;
else x=(pos+*prev(it))>>1;
mp[x]=t;
}
{
int x=0;
if (it==st.end()) x=inf+pos;
else x=(*it+pos)>>1;
mp[x]=t;
}
st.emplace_hint(it, pos);
}else{
{
int x=0, y=0;
if (it==st.begin()) x=-pos, y=pos*2;
else x=(pos+*prev(it))>>1, y=(pos-*prev(it))>>1;
events.push_back({mp[x], t-1, x, y});
mp.erase(x);
}
{
int x=0, y=0;
if (next(it)==st.end()) x=inf+pos, y=inf;
else x=(*next(it)+pos)>>1, y=(*next(it)-pos)>>1;
events.push_back({mp[x], t-1, x, y});
mp.erase(x);
}
if ((int)st.size()>1){
int x=0;
if (it==st.begin()) x=-*next(it);
else if (next(it)==st.end()) x=inf+*prev(it);
else x=(*next(it)+*prev(it))>>1;
mp[x]=t;
}
st.erase(it);
}
}
}
for (auto &i:events){
vpos.push_back(i[2]);
}
sort(vpos.begin(), vpos.end()); vpos.resize(unique(vpos.begin(), vpos.end())-vpos.begin());
vector<pair<int, int>> query(q);
for (auto &i:query) cin >> i.first >> i.second, vtime.push_back(i.second), i.first*=2;
sort(vtime.begin(), vtime.end()); vtime.resize(unique(vtime.begin(), vtime.end())-vtime.begin());
for (int i=1; i<=q; ++i){
int pl=lower_bound(vpos.begin(), vpos.end(), query[i-1].first)-vpos.begin();
int pr=upper_bound(vpos.begin(), vpos.end(), query[i-1].first)-vpos.begin()-1;
vq[lower_bound(vtime.begin(), vtime.end(), query[i-1].second)-vtime.begin()].push_back({{pr, pl}, {i, query[i-1].first}});
check.push_back({query[i-1].second, {2, i}});
}
stl.init((int)vpos.size()-1);
str.init((int)vpos.size()-1);
st.init((int)vtime.size()-1);
for (auto &i:events){
i[0]=lower_bound(vtime.begin(), vtime.end(), i[0])-vtime.begin();
i[1]=upper_bound(vtime.begin(), vtime.end(), i[1])-vtime.begin()-1;
st.update(1, 1, st.n, i[0], i[1], {lower_bound(vpos.begin(), vpos.end(), i[2])-vpos.begin(), {i[2], i[3]}});
}
st.dfs(1, 1, st.n);
sort(check.begin(), check.end());
vector<int> cnt(k+1); int cnt0=k;
for (auto &i:check){
if (abs(i.second.first)==1){
cnt0-=!cnt[i.second.second];
cnt[i.second.second]+=i.second.first;
cnt0+=!cnt[i.second.second];
}else{
if (cnt0) ans[i.second.second]=-1;
}
}
for (int i=1; i<=q; ++i) cout << ans[i] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
141460 KB |
Output is correct |
| 2 |
Correct |
67 ms |
141396 KB |
Output is correct |
| 3 |
Correct |
65 ms |
141456 KB |
Output is correct |
| 4 |
Incorrect |
62 ms |
141464 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
141460 KB |
Output is correct |
| 2 |
Correct |
67 ms |
141396 KB |
Output is correct |
| 3 |
Correct |
65 ms |
141456 KB |
Output is correct |
| 4 |
Incorrect |
62 ms |
141464 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1703 ms |
301008 KB |
Output is correct |
| 2 |
Incorrect |
1484 ms |
299716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5116 ms |
411944 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
141460 KB |
Output is correct |
| 2 |
Correct |
67 ms |
141396 KB |
Output is correct |
| 3 |
Correct |
65 ms |
141456 KB |
Output is correct |
| 4 |
Incorrect |
62 ms |
141464 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
141460 KB |
Output is correct |
| 2 |
Correct |
67 ms |
141396 KB |
Output is correct |
| 3 |
Correct |
65 ms |
141456 KB |
Output is correct |
| 4 |
Incorrect |
62 ms |
141464 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
