#include <bits/stdc++.h>
#pragma gcc optimize "03"
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)
{
//for(auto it : comp) printf("%d ", it); printf("-> %d\n", x);
//assert(binary_search(comp.begin(), comp.end(), x));
return lower_bound(comp.begin(), comp.end(), x)-comp.begin();
}
priority_queue<int, vector<int>, less<int>> tree1[5*MAXN+10];
priority_queue<int, vector<int>, less<int>> dead1[5*MAXN+10];
priority_queue<int, vector<int>, greater<int>> tree2[5*MAXN+10];
priority_queue<int, vector<int>, greater<int>> dead2[5*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)
{
//printf("INSERT2 %d %d\n", x, y);
swap(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);
}
int last=0;
for(i=1; i<=Q; i++)
{
int l, x;
scanf("%d%d", &x, &l); x*=2;
query.push_back({l, x, -i, 0});
last=max(last, l);
scomp.insert(x);
}
sort(query.begin(), query.end());
scomp.insert(0); scomp.insert(2e8);
for(auto now : query)
{
int x=now.x;
if(now.p==1)
{
if(S[now.k].find(x)==S[now.k].end())
{
if(S[now.k].size()!=0)
{
auto it=S[now.k].lower_bound(x);
int r=*it, l=*prev(it);
if(it==S[now.k].end()) scomp.insert(l+x>>1);
else if(it==S[now.k].begin()) scomp.insert(r+x>>1);
else
{
scomp.insert(l+x>>1);
scomp.insert(r+x>>1);
}
}
}
S[now.k].insert(x);
}
else if(now.p==-1)
{
S[now.k].erase(S[now.k].find(x));
if(S[now.k].find(x)==S[now.k].end())
{
if(S[now.k].size()!=0)
{
auto it=S[now.k].lower_bound(x);
int r=*it, l=*prev(it);
if(it==S[now.k].end());
else if(it==S[now.k].begin());
else scomp.insert(l+r>>1);
}
}
}
}
comp.push_back(-1);
for(auto it : scomp) comp.push_back(it);
SZ=scomp.size();
for(i=1; i<=K; i++) S[i].clear();
for(auto now : query)
{
//printf("===============\n");
if(last<now.t) break;
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=*prev(it);
if(it==S[now.k].end())
{
insert2(l, l+x>>1);
insert1(l+x>>1, x);
insert2(x, 2e8);
}
else if(it==S[now.k].begin())
{
insert1(0, x);
insert2(x, r+x>>1);
insert1(r+x>>1, r);
}
else
{
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=*prev(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:2:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
#pragma gcc optimize "03"
new_home.cpp: In function 'int main()':
new_home.cpp:156:58: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
if(it==S[now.k].end()) scomp.insert(l+x>>1);
~^~
new_home.cpp:157:65: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
else if(it==S[now.k].begin()) scomp.insert(r+x>>1);
~^~
new_home.cpp:160:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
scomp.insert(l+x>>1);
~^~
new_home.cpp:161:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
scomp.insert(r+x>>1);
~^~
new_home.cpp:178:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
else scomp.insert(l+r>>1);
~^~
new_home.cpp:217:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert2(l, l+x>>1);
~^~
new_home.cpp:218:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert1(l+x>>1, x);
~^~
new_home.cpp:224:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert2(x, r+x>>1);
~^~
new_home.cpp:225:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert1(r+x>>1, r);
~^~
new_home.cpp:229:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert2(l, l+x>>1);
~^~
new_home.cpp:230:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert1(l+x>>1, x);
~^~
new_home.cpp:231:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert2(x, x+r>>1);
~^~
new_home.cpp:232:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert1(x+r>>1, r);
~^~
new_home.cpp:256:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase2(l, l+x>>1);
~^~
new_home.cpp:257:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase1(l+x>>1, x);
~^~
new_home.cpp:264:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase2(x, r+x>>1);
~^~
new_home.cpp:265:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase1(r+x>>1, r);
~^~
new_home.cpp:269:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert2(l, l+r>>1);
~^~
new_home.cpp:270:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
insert1(l+r>>1, r);
~^~
new_home.cpp:271:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase2(l, l+x>>1);
~^~
new_home.cpp:272:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase1(l+x>>1, x);
~^~
new_home.cpp:273:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase2(x, x+r>>1);
~^~
new_home.cpp:274:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
erase1(x+r>>1, r);
~^~
new_home.cpp:122:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
new_home.cpp:124: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:128: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:137: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 |
190 ms |
202348 KB |
Output is correct |
| 2 |
Correct |
187 ms |
202232 KB |
Output is correct |
| 3 |
Correct |
217 ms |
202288 KB |
Output is correct |
| 4 |
Incorrect |
216 ms |
202364 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
190 ms |
202348 KB |
Output is correct |
| 2 |
Correct |
187 ms |
202232 KB |
Output is correct |
| 3 |
Correct |
217 ms |
202288 KB |
Output is correct |
| 4 |
Incorrect |
216 ms |
202364 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4309 ms |
375088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5112 ms |
423028 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
190 ms |
202348 KB |
Output is correct |
| 2 |
Correct |
187 ms |
202232 KB |
Output is correct |
| 3 |
Correct |
217 ms |
202288 KB |
Output is correct |
| 4 |
Incorrect |
216 ms |
202364 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
190 ms |
202348 KB |
Output is correct |
| 2 |
Correct |
187 ms |
202232 KB |
Output is correct |
| 3 |
Correct |
217 ms |
202288 KB |
Output is correct |
| 4 |
Incorrect |
216 ms |
202364 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
