#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)3e5 + 10;
const int M = N * 4;
int x[N];
int a[N];
int b[N];
int t[N];
vector<int> bb;
multiset <int> P[N];
int cum;
void add(int id, int v){ // = 2n points
bb.push_back(v);
auto it = P[id].insert(v);
auto nx = it;
nx ++ ;
if(nx != P[id].end()){
cum = v + (*nx);
if(cum % 2 == 0){
bb.push_back(cum/2);
}
else{
bb.push_back(cum/2);
bb.push_back(cum/2+1);
}
}
nx = it;
if(nx != P[id].begin()){
nx -- ;
cum = v + (*nx);
if(cum % 2 == 0){
bb.push_back(cum/2);
}
else{
bb.push_back(cum/2);
bb.push_back(cum/2+1);
}
}
}
void delet(int id, int v){
auto it = P[id].lower_bound(v);
auto nx = it;
nx ++ ;
auto pv = it;
if(pv != P[id].begin() && nx != P[id].end()){
cum = (*pv + *nx);
pv--;
if(cum % 2 == 0){
bb.push_back(cum/2);
}
else{
bb.push_back(cum/2);
bb.push_back(cum/2+1);
}
}
P[id].erase(it);
}
multiset<int> Q[2][M*4+12];
void ins(int node, int cl, int cr, int tl, int tr, int dir, int v, int mode){
if(cr < tl || cl > tr) return;
if(cl >= tl && cr <= tr){
if(mode == 0)
Q[dir][node].insert(v);
else
Q[dir][node].erase(Q[dir][node].find(v));
return;
}
int mid = (cl + cr) / 2;
ins(node * 2, cl, mid, tl, tr, dir, v, mode);
ins(node * 2 + 1, mid + 1, cr, tl, tr, dir, v, mode);
}
int get(int node, int cl, int cr, int pos){
int vl = 0;
if(!Q[0][node].empty()){ // O(1) ????????
auto it = Q[0][node].end();
-- it;
vl = max(vl, bb[pos]+*it);
}
if(!Q[1][node].empty()){
auto it = Q[1][node].end();
-- it;
vl=max(vl,*it-bb[pos]);
}
if(cl == cr) return vl;
int mid = (cl + cr) / 2;
if(mid >= pos)
vl = max(vl, get(node*2,cl,mid,pos));
else
vl=max(vl, get(node*2+1,mid+1,cr,pos));
return vl;
}
int ln[N];
int yr[N];
int cnt[N];
int tot;
int getid(int ff){
return lower_bound(bb.begin(), bb.end(), ff) - bb.begin();
}
int m;
void add_f(int li, int ri, int mode){
if(li == -(int)1e9 && ri == (int)1e9) return;
cum = (li + ri);
if(cum % 2 == 0){
ins(1, 0, m - 1, getid(li), getid(cum/2),0,-li,mode);
ins(1, 0, m - 1, getid(cum/2), getid(ri),1,ri,mode);
}
else{
ins(1, 0, m - 1, getid(li), getid(cum/2),0,-(li),mode);
ins(1, 0, m - 1, getid(cum/2+1), getid(ri),1,(ri),mode);
}
}
int soln[N];
int main(){
fastIO;
int n, k, q;
cin >> n >> k >> q;
vector<pii> eve;
for(int i = 1; i <= n; i ++ ){
cin >> x[i] >> t[i] >> a[i] >> b[i];
eve.push_back(mp(a[i], i));
eve.push_back(mp(b[i] + 1, i));
}
sort(eve.begin(), eve.end());
for(int i = 1; i <= k ; i ++ ){
P[i].insert(-(int)1e9);
P[i].insert((int)1e9);
}
bb.push_back(-(int)1e9);
bb.push_back((int)1e9); // logs stay ~ the same doesn't make a diff
for(auto q : eve){
if(q.fi == a[q.se]){
add(t[q.se], x[q.se]);
}
else{
delet(t[q.se], x[q.se]);
}
}
vector<pii> qq;
for(int i = 1; i <= q; i ++ ){
cin >> ln[i] >> yr[i];
qq.push_back(mp(yr[i], i));
bb.push_back(ln[i]);
}
bb.push_back(0);
sort(bb.begin(), bb.end());
bb.resize(unique(bb.begin(), bb.end()) - bb.begin());
m = bb.size();
sort(qq.begin(), qq.end());
int iq = 0;
int id;
for(auto p : qq){
while(iq < eve.size() && eve[iq].fi <= p.fi){
id = eve[iq].se;
if(eve[iq].fi == a[eve[iq].se]){
cnt[t[id]] ++ ;
if(cnt[t[id]] == 1) tot ++ ;
auto it = P[t[id]].insert(x[id]);
auto pv = it;
auto nx = it;
nx ++ ;
if(nx != P[t[id]].end()){
add_f(*it, *nx, 0);
}
if(pv != P[t[id]].begin()){
pv -- ;
add_f(*pv, *it, 0);
}
}
else{
cnt[t[id]] -- ;
if(cnt[t[id]] == 0) tot -- ;
auto it = P[t[id]].lower_bound(x[id]);
auto pv = it;
auto nx = it;
nx ++ ;
bool big = true;
if(nx != P[t[id]].end()){
add_f(*it, *nx, 1);
}
else big = false;
if(pv != P[t[id]].begin()){
pv -- ;
add_f(*pv, *it, 1);
}
else big = false;
if(big){
add_f(*pv, *nx, 0);
}
P[t[id]].erase(it);
}
iq ++ ;
}
if(tot == k){
soln[p.se]=get(1, 0, m - 1, getid(ln[p.se]));
}
else{
soln[p.se]=-1;
}
}
for(int i = 1; i <= q; i ++ ){
cout << soln[i] << "\n";
}
return 0;
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:180:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
180 | while(iq < eve.size() && eve[iq].fi <= p.fi){
| ~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
301 ms |
465412 KB |
Output is correct |
| 2 |
Correct |
300 ms |
465408 KB |
Output is correct |
| 3 |
Correct |
299 ms |
465516 KB |
Output is correct |
| 4 |
Incorrect |
295 ms |
465388 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
301 ms |
465412 KB |
Output is correct |
| 2 |
Correct |
300 ms |
465408 KB |
Output is correct |
| 3 |
Correct |
299 ms |
465516 KB |
Output is correct |
| 4 |
Incorrect |
295 ms |
465388 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5146 ms |
806744 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5138 ms |
793100 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
301 ms |
465412 KB |
Output is correct |
| 2 |
Correct |
300 ms |
465408 KB |
Output is correct |
| 3 |
Correct |
299 ms |
465516 KB |
Output is correct |
| 4 |
Incorrect |
295 ms |
465388 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
301 ms |
465412 KB |
Output is correct |
| 2 |
Correct |
300 ms |
465408 KB |
Output is correct |
| 3 |
Correct |
299 ms |
465516 KB |
Output is correct |
| 4 |
Incorrect |
295 ms |
465388 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
