#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 3e5;
const int MAXVAL = 1e8;
struct Query
{
int t, x, k, p;
bool operator < (const Query &p)
{
if(t!=p.t) return t<p.t;
return k>p.k;
}
};
int N, K, Q, ans[MAXN+10], SZ, chk;
vector<Query> query;
multiset<int> S[MAXN+10];
set<int> scomp;
vector<int> comp;
int getcomp(int x) { return lower_bound(comp.begin(), comp.end(), x)-comp.begin(); }
priority_queue<int, vector<int>, less<int>> tree1[4*MAXN+10];
priority_queue<int, vector<int>, less<int>> dead1[4*MAXN+10];
priority_queue<int, vector<int>, greater<int>> tree2[4*MAXN+10];
priority_queue<int, vector<int>, greater<int>> dead2[4*MAXN+10];
ll query1(int x)
{
int y=x;
x=getcomp(x);
int ret=0;
for(; x>0; x-=(x&-x))
{
while(!tree1[x].empty() && !dead1[x].empty() && tree1[x].top()==dead1[x].top()) tree1[x].pop(), dead1[x].pop();
if(!tree1[x].empty())
{
//printf("QUERY1 %d %d\n", x, tree1[x].top()-y);
ret=max(ret, tree1[x].top()-y);
}
}
return ret;
}
void erase1(int x, int y)
{
//printf("ERASE1 %d %d\n", x, y);
x=getcomp(x);
for(; x<=SZ; x+=(x&-x))
{
dead1[x].push(y);
}
}
void insert1(int x, int y)
{
//printf("INSERT1 %d %d\n", x, y);
x=getcomp(x);
for(; x<=SZ; x+=(x&-x))
{
tree1[x].push(y);
}
}
ll query2(int x)
{
int y=x;
x=getcomp(x);
x=SZ-x+1;
int ret=0;
for(; x>0; x-=(x&-x))
{
while(!tree2[x].empty() && !dead2[x].empty() && tree2[x].top()==dead2[x].top()) tree2[x].pop(), dead2[x].pop();
if(!tree2[x].empty())
{
//printf("QUERY1 %d %d\n", x, y-tree2[x].top());
ret=max(ret, y-tree2[x].top());
}
}
return ret;
}
void erase2(int x, int y)
{
swap(x, y);
//printf("ERASE2 %d %d\n", x, y);
x=getcomp(x);
x=SZ-x+1;
for(; x<=SZ; x+=(x&-x))
{
dead2[x].push(y);
}
}
void insert2(int x, int y)
{
swap(x, y);
//printf("INSERT2 %d %d\n", x, y);
x=getcomp(x);
x=SZ-x+1;
for(; x<=SZ; x+=(x&-x))
{
tree2[x].push(y);
}
}
int main()
{
int i, j;
scanf("%d%d%d", &N, &K, &Q);
for(i=1; i<=N; i++)
{
int x, t, a, b;
scanf("%d%d%d%d", &x, &t, &a, &b); b++; x*=2;
query.push_back({a, x, t, 1});
query.push_back({b, x, t, -1});
scomp.insert(x);
}
for(i=1; i<=Q; i++)
{
int l, x;
scanf("%d%d", &x, &l); x*=2;
query.push_back({l, x, -i, 0});
scomp.insert(x);
}
sort(query.begin(), query.end());
for(i=1; i<=N; i++) S[i].insert(0), S[i].insert(2e8);
scomp.insert(0); scomp.insert(2e8);
for(auto now : query)
{
if(now.p==1)
{
if(S[now.k].find(now.x)!=S[now.k].end())
{
auto it=S[now.k].lower_bound(now.x);
int r=*it, l=*(--it);
scomp.insert(l+now.x>>1);
scomp.insert(r+now.x>>1);
}
S[now.k].insert(now.x);
}
else if(now.p==-1) S[now.k].erase(S[now.k].find(now.x));
}
comp.push_back(-1);
for(auto it : scomp) comp.push_back(it);
SZ=comp.size()-1;
for(i=1; i<=N; i++) S[i].clear();
for(auto now : query)
{
//printf("===============\n");
int x=now.x;
if(now.p==0)
{
if(chk!=K) ans[-now.k]=-1;
else ans[-now.k]=max(query1(x), query2(x))>>1;
//printf("!%d %d %d\n", -now.k, query1(x), query2(x));
}
else if(now.p==1)
{
if(S[now.k].find(now.x)==S[now.k].end())
{
if(S[now.k].size()==0)
{
insert1(0, x);
insert2(x, 2e8);
chk++;
}
else
{
auto it=S[now.k].lower_bound(x);
int r=*it, l=*(--it);
if(it==S[now.k].end())
{
erase2(l, 2e8);
insert2(l, l+x>>1);
insert1(l+x>>1, x);
insert2(x, 2e8);
}
else if(it==S[now.k].begin())
{
erase1(0, r);
insert1(0, x);
insert2(x, r+x>>1);
insert1(r+x>>1, r);
}
else
{
erase2(l, l+r>>1);
erase1(l+r>>1, r);
insert2(l, l+x>>1);
insert1(l+x>>1, x);
insert2(x, x+r>>1);
insert1(x+r>>1, r);
}
}
}
S[now.k].insert(now.x);
}
else if(now.p==-1)
{
S[now.k].erase(S[now.k].find(now.x));
if(S[now.k].find(now.x)==S[now.k].end())
{
if(S[now.k].size()==0)
{
erase1(0, x);
erase2(x, 2e8);
chk--;
}
else
{
auto it=S[now.k].lower_bound(x);
int r=*it, l=*(--it);
if(it==S[now.k].end())
{
insert2(l, 2e8);
erase2(l, l+x>>1);
erase1(l+x>>1, x);
erase2(x, 2e8);
}
else if(it==S[now.k].begin())
{
insert1(0, r);
erase1(0, x);
erase2(x, r+x>>1);
erase1(r+x>>1, r);
}
else
{
insert2(l, l+r>>1);
insert1(l+r>>1, r);
erase2(l, l+x>>1);
erase1(l+x>>1, x);
erase2(x, x+r>>1);
erase1(x+r>>1, r);
}
}
}
}
}
for(i=1; i<=Q; i++) printf("%d\n", ans[i]);
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:146:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
scomp.insert(l+now.x>>1);
~^~~~~~
new_home.cpp:147:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
scomp.insert(r+now.x>>1);
~^~~~~~
new_home.cpp:187:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert2(l, l+x>>1);
~^~
new_home.cpp:188:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert1(l+x>>1, x);
~^~
new_home.cpp:195:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert2(x, r+x>>1);
~^~
new_home.cpp:196:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert1(r+x>>1, r);
~^~
new_home.cpp:200:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase2(l, l+r>>1);
~^~
new_home.cpp:201:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase1(l+r>>1, r);
~^~
new_home.cpp:202:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert2(l, l+x>>1);
~^~
new_home.cpp:203:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert1(l+x>>1, x);
~^~
new_home.cpp:204:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert2(x, x+r>>1);
~^~
new_home.cpp:205:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert1(x+r>>1, r);
~^~
new_home.cpp:229:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase2(l, l+x>>1);
~^~
new_home.cpp:230:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase1(l+x>>1, x);
~^~
new_home.cpp:237:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase2(x, r+x>>1);
~^~
new_home.cpp:238:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase1(r+x>>1, r);
~^~
new_home.cpp:242:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert2(l, l+r>>1);
~^~
new_home.cpp:243:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert1(l+r>>1, r);
~^~
new_home.cpp:244:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase2(l, l+x>>1);
~^~
new_home.cpp:245:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase1(l+x>>1, x);
~^~
new_home.cpp:246:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase2(x, x+r>>1);
~^~
new_home.cpp:247:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase1(x+r>>1, r);
~^~
new_home.cpp:116:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
new_home.cpp:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &N, &K, &Q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &x, &t, &a, &b); b++; x*=2;
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:130:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &l); x*=2;
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
164728 KB |
Output is correct |
| 2 |
Correct |
149 ms |
164700 KB |
Output is correct |
| 3 |
Correct |
150 ms |
164728 KB |
Output is correct |
| 4 |
Incorrect |
172 ms |
164856 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
164728 KB |
Output is correct |
| 2 |
Correct |
149 ms |
164700 KB |
Output is correct |
| 3 |
Correct |
150 ms |
164728 KB |
Output is correct |
| 4 |
Incorrect |
172 ms |
164856 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5104 ms |
417524 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5105 ms |
373684 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
164728 KB |
Output is correct |
| 2 |
Correct |
149 ms |
164700 KB |
Output is correct |
| 3 |
Correct |
150 ms |
164728 KB |
Output is correct |
| 4 |
Incorrect |
172 ms |
164856 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
150 ms |
164728 KB |
Output is correct |
| 2 |
Correct |
149 ms |
164700 KB |
Output is correct |
| 3 |
Correct |
150 ms |
164728 KB |
Output is correct |
| 4 |
Incorrect |
172 ms |
164856 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
