#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);
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);
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);
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();
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 if(S[now.k].size()==1)
{
int l=*S[now.k].begin();
if(l<x)
{
erase2(l, 2e8);
insert2(l, l+x>>1);
insert1(l+x>>1, x);
insert2(x, 2e8);
}
else
{
erase1(0, l);
insert1(0, x);
insert2(x, l+x>>1);
insert1(l+x>>1, l);
}
}
else
{
auto it=S[now.k].lower_bound(x);
int r=*it, l=*(--it);
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 if(S[now.k].size()==1)
{
int l=*S[now.k].begin();
if(l<x)
{
insert2(l, 2e8);
erase2(l, l+x>>1);
erase1(l+x>>1, x);
erase2(x, 2e8);
}
else
{
insert1(0, l);
erase1(0, x);
erase2(x, l+x>>1);
erase1(l+x>>1, l);
}
}
else
{
auto it=S[now.k].lower_bound(x);
int r=*it, l=*(--it);
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:143:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
scomp.insert(l+now.x>>1);
~^~~~~~
new_home.cpp:144:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
scomp.insert(r+now.x>>1);
~^~~~~~
new_home.cpp:183:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert2(l, l+x>>1);
~^~
new_home.cpp:184:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert1(l+x>>1, x);
~^~
new_home.cpp:191:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert2(x, l+x>>1);
~^~
new_home.cpp:192:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert1(l+x>>1, l);
~^~
new_home.cpp:199:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase2(l, l+r>>1);
~^~
new_home.cpp:200:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase1(l+r>>1, r);
~^~
new_home.cpp:201:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert2(l, l+x>>1);
~^~
new_home.cpp:202:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert1(l+x>>1, x);
~^~
new_home.cpp:203:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert2(x, x+r>>1);
~^~
new_home.cpp:204:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert1(x+r>>1, r);
~^~
new_home.cpp:226:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase2(l, l+x>>1);
~^~
new_home.cpp:227:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase1(l+x>>1, x);
~^~
new_home.cpp:234:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase2(x, l+x>>1);
~^~
new_home.cpp:235:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase1(l+x>>1, l);
~^~
new_home.cpp:242:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert2(l, l+r>>1);
~^~
new_home.cpp:243:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert1(l+r>>1, r);
~^~
new_home.cpp:244:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase2(l, l+x>>1);
~^~
new_home.cpp:245:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase1(l+x>>1, x);
~^~
new_home.cpp:246:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase2(x, x+r>>1);
~^~
new_home.cpp:247:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase1(x+r>>1, r);
~^~
new_home.cpp:113:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
new_home.cpp:115: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:119: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:127: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 |
153 ms |
164728 KB |
Output is correct |
| 2 |
Correct |
153 ms |
164712 KB |
Output is correct |
| 3 |
Correct |
178 ms |
164696 KB |
Output is correct |
| 4 |
Incorrect |
151 ms |
164720 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
164728 KB |
Output is correct |
| 2 |
Correct |
153 ms |
164712 KB |
Output is correct |
| 3 |
Correct |
178 ms |
164696 KB |
Output is correct |
| 4 |
Incorrect |
151 ms |
164720 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5118 ms |
385788 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5098 ms |
381636 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
164728 KB |
Output is correct |
| 2 |
Correct |
153 ms |
164712 KB |
Output is correct |
| 3 |
Correct |
178 ms |
164696 KB |
Output is correct |
| 4 |
Incorrect |
151 ms |
164720 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
153 ms |
164728 KB |
Output is correct |
| 2 |
Correct |
153 ms |
164712 KB |
Output is correct |
| 3 |
Correct |
178 ms |
164696 KB |
Output is correct |
| 4 |
Incorrect |
151 ms |
164720 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
