#pragma GCC optimize("arch=skylake")
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
const int INF = 1e9+5;
vector<pair<int, pair<int, int>>> ev;
vector<int> cp, cpy;
int n, q, k;
int ans[maxn];
int p[maxn], ty[maxn];
int L[maxn], Y[maxn];
int st[4*maxn][2];
struct ev_upd{
int l, r, ty;
ev_upd(int _l, int _r, int _ty): l(_l), r(_r), ty(_ty){};
};
map<int, vector<pair<int, int>>> leaf_q;
set<pair<int, int>> pos[maxn];
int last_time[maxn][2];
vector<ev_upd> st_time[4*maxn];
int crrt;
pair<pair<int, int>, int> undo_stack[maxn*20];
int stksz = 0;
// 0 is min, 1 is max
void upd_st(const ev_upd &ele, int &cnt, int l = 0, int r = cp.size()-1, int id = 1){
if(ele.l > ele.r || ele.l > cp[r] || ele.r < cp[l])return;
if(ele.l <= cp[l] && cp[r] <= ele.r){
if(ele.ty == 0){
if(st[id][0] > ele.l){
undo_stack[stksz++] = make_pair(make_pair(id, 0), st[id][0]);
st[id][0] = ele.l;
cnt++;
}
}
else {
if(st[id][1] < ele.r){
undo_stack[stksz++] = make_pair(make_pair(id, 1), st[id][1]);
st[id][1] = ele.r;
cnt++;
}
}
}
else {
int mid = (l+r)>>1;
upd_st(ele, cnt, l, mid, id<<1);
upd_st(ele, cnt, mid+1, r, id<<1|1);
}
}
int query_st(int pos, int l = 0, int r = cp.size()-1, int id = 1){
int re = max(st[id][1] - pos, pos - st[id][0]);
if(l < r){
int mid = (l + r)>>1;
if(pos <= cp[mid])re = max(re, query_st(pos, l, mid, id<<1));
else re = max(re, query_st(pos, mid+1, r, id<<1|1));
}
return re;
}
void time_add(int ql, int qr, const ev_upd &ele, int l = 0, int r = cpy.size()-1, int id = 1){
if(ql > cpy[r] || qr < cpy[l])return;
if(ql <= cpy[l] && cpy[r] <= qr)st_time[id].push_back(ele);
else {
int mid = (l+r)>>1;
time_add(ql, qr, ele, l, mid, id<<1);
time_add(ql, qr, ele, mid+1, r, id<<1|1);
}
}
int sumcol[maxn];
int sumall = 0, ptr = 0;
void time_dfs(int l = 0, int r = cpy.size()-1, int id = 1){
int cnt = 0;
for(auto ele: st_time[id]) {
upd_st(ele, cnt);
}
if(l == r){
while(ptr < ev.size() && ev[ptr].first <= cpy[l]){
if(ev[ptr].second.first){
sumcol[ty[ev[ptr].second.second]]--;
if(!sumcol[ty[ev[ptr].second.second]])sumall--;
}
else {
if(!sumcol[ty[ev[ptr].second.second]])sumall++;
sumcol[ty[ev[ptr].second.second]]++;
}
ptr++;
}
// cout << sumall << endl;
for(auto qq: leaf_q[cpy[l]]){
ans[qq.second] = sumall < k ? -1 : query_st(qq.first);
}
}
else {
int mid = (l+r)>>1;
time_dfs(l, mid, id<<1);
time_dfs(mid+1, r, id<<1|1);
}
for(int i = 0; i < cnt; i++){
stksz--;
st[undo_stack[stksz].first.first][undo_stack[stksz].first.second] = undo_stack[stksz].second;
}
}
void add_range(int l, int r){
if(l != -INF)last_time[l][0] = crrt;
if(r != INF)last_time[r][1] = crrt;
}
void del_range(int l, int r){
// return;
if(l == -INF){
assert(last_time[r][1]);
ev_upd ele(-INF, p[r], 1);
time_add(last_time[r][1], crrt-1, ele);
}
else if(r == INF){
assert(last_time[l][0]);
time_add(last_time[l][0], crrt-1, ev_upd(p[l], INF, 0));
}
else {
assert(last_time[l][0]);
assert(last_time[r][1]);
int mid = (l+r)/2;
time_add(last_time[l][0], crrt-1, ev_upd(p[l], mid, 0));
time_add(last_time[r][1], crrt-1, ev_upd(mid+1, p[r], 1));
}
}
void add(int x, int col){
// cout << x << endl;
auto it = pos[col].insert(make_pair(p[x], x)).first;
if(pos[col].size() == 1){
add_range(-INF, x);
add_range(x, INF);
}
else {
if(next(it) == pos[col].end()){
int prv = prev(it)->second;
del_range(prv, INF);
add_range(prv, x);
add_range(x, INF);
}
else if(it == pos[col].begin()){
int nxt = next(it)->second;
del_range(-INF, nxt);
add_range(-INF, x);
add_range(x, nxt);
}
else {
int prv = prev(it)->second;
int nxt = next(it)->second;
del_range(prv, nxt);
add_range(prv, x);
add_range(x, nxt);
}
}
}
void del(int x, int col){
// cout << "DEL " << x << endl;
auto it = pos[col].erase(pos[col].find(make_pair(p[x], x)));
if(pos[col].size() == 0){
del_range(-INF, x);
del_range(x, INF);
}
else {
if(it == pos[col].end()){
int prv = prev(it)->second;
del_range(x, INF);
del_range(prv, x);
add_range(prv, INF);
}
else if(it == pos[col].begin()){
int nxt = it->second;
del_range(-INF, x);
del_range(x, nxt);
add_range(-INF, nxt);
}
else {
int prv = prev(it)->second;
int nxt = it->second;
del_range(x, nxt);
del_range(prv, x);
add_range(prv, nxt);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k >> q;
for(int i = 0; i < 4*maxn; i++)st[i][0] = INF, st[i][1] = -INF;
for(int i = 1; i <= n; i++){
int a, b;
cin >> p[i] >> ty[i] >> a >> b;
ev.push_back({a, {0, i}});
ev.push_back({b+1, {1, i}});
}
for(int i = 1; i <= q; i++){
cin >> L[i] >> Y[i];
cp.push_back(L[i]);
cpy.push_back(Y[i]);
leaf_q[Y[i]].push_back({L[i], i});
}
sort(cp.begin(), cp.end());
cp.erase(unique(cp.begin(), cp.end()), cp.end());
sort(cpy.begin(), cpy.end());
cpy.erase(unique(cpy.begin(), cpy.end()), cpy.end());
sort(ev.begin(), ev.end());
for(auto v: ev){
crrt = v.first;
if(v.second.first)del(v.second.second, ty[v.second.second]);
else add(v.second.second , ty[v.second.second]);
}
// cout << "SUS" << endl;
// if(n > 100000)return 0;
time_dfs();
for(int i = 1; i <= q; i++)cout << ans[i] << "\n";
}
Compilation message
new_home.cpp:1:36: warning: bad option '-farch=skylake' to pragma 'optimize' [-Wpragmas]
1 | #pragma GCC optimize("arch=skylake")
| ^
new_home.cpp:20:35: warning: bad option '-farch=skylake' to attribute 'optimize' [-Wattributes]
20 | ev_upd(int _l, int _r, int _ty): l(_l), r(_r), ty(_ty){};
| ^
new_home.cpp:37:84: warning: bad option '-farch=skylake' to attribute 'optimize' [-Wattributes]
37 | void upd_st(const ev_upd &ele, int &cnt, int l = 0, int r = cp.size()-1, int id = 1){
| ^
new_home.cpp:62:65: warning: bad option '-farch=skylake' to attribute 'optimize' [-Wattributes]
62 | int query_st(int pos, int l = 0, int r = cp.size()-1, int id = 1){
| ^
new_home.cpp:72:93: warning: bad option '-farch=skylake' to attribute 'optimize' [-Wattributes]
72 | void time_add(int ql, int qr, const ev_upd &ele, int l = 0, int r = cpy.size()-1, int id = 1){
| ^
new_home.cpp:85:58: warning: bad option '-farch=skylake' to attribute 'optimize' [-Wattributes]
85 | void time_dfs(int l = 0, int r = cpy.size()-1, int id = 1){
| ^
new_home.cpp: In function 'void time_dfs(int, int, int)':
new_home.cpp:91:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | while(ptr < ev.size() && ev[ptr].first <= cpy[l]){
| ~~~~^~~~~~~~~~~
new_home.cpp: At global scope:
new_home.cpp:119:28: warning: bad option '-farch=skylake' to attribute 'optimize' [-Wattributes]
119 | void add_range(int l, int r){
| ^
new_home.cpp:124:28: warning: bad option '-farch=skylake' to attribute 'optimize' [-Wattributes]
124 | void del_range(int l, int r){
| ^
new_home.cpp:144:24: warning: bad option '-farch=skylake' to attribute 'optimize' [-Wattributes]
144 | void add(int x, int col){
| ^
new_home.cpp:174:24: warning: bad option '-farch=skylake' to attribute 'optimize' [-Wattributes]
174 | void del(int x, int col){
| ^
new_home.cpp:204:10: warning: bad option '-farch=skylake' to attribute 'optimize' [-Wattributes]
204 | int main() {
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
56148 KB |
Output is correct |
| 2 |
Correct |
13 ms |
56156 KB |
Output is correct |
| 3 |
Correct |
14 ms |
56156 KB |
Output is correct |
| 4 |
Incorrect |
18 ms |
55280 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
56148 KB |
Output is correct |
| 2 |
Correct |
13 ms |
56156 KB |
Output is correct |
| 3 |
Correct |
14 ms |
56156 KB |
Output is correct |
| 4 |
Incorrect |
18 ms |
55280 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
909 ms |
148840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4493 ms |
333468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
56148 KB |
Output is correct |
| 2 |
Correct |
13 ms |
56156 KB |
Output is correct |
| 3 |
Correct |
14 ms |
56156 KB |
Output is correct |
| 4 |
Incorrect |
18 ms |
55280 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
56148 KB |
Output is correct |
| 2 |
Correct |
13 ms |
56156 KB |
Output is correct |
| 3 |
Correct |
14 ms |
56156 KB |
Output is correct |
| 4 |
Incorrect |
18 ms |
55280 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
