This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
typedef vector<int> vi;
#define iii tuple<int,int,int>
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef map<int,int> mii;
struct node{
int32_t s,e;
int mn,mx,sum,add_val,set_val;
bool lset;
node *l, *r;
node (int _s, int _e, int A[]=NULL): s(_s), e(_e), mn(0), mx(0), sum(0), lset(0), add_val(0), set_val(0), l(NULL), r(NULL){
if (A==NULL) return;
if (s==e) mn=mx=sum=A[s];
else{
l=new node(s, (s+e)>>1,A), r=new node((s+e+2)>>1,e,A);
combine();
}
}
void create_children(){
if (s==e) return;
if (l!=NULL) return;
int m=(s+e)>>1;
l=new node(s,m);
r=new node(m+1,e);
}
void self_set(int v){
lset=1;
mn=mx=set_val=v;
sum=v*(e-s+1);
add_val=0;
}
void self_add(int v){
if (lset) {self_set(v+set_val); return;}
mn+=v, mx+=v, add_val+=v;
sum+=v*(e-s+1);
}
void lazy(){
if (s==e) return;
if (lset){
l->self_set(set_val), r->self_set(set_val);
set_val=0; lset=0;
}
if (add_val!=0){
l->self_add(add_val), r->self_add(add_val);
add_val=0;
}
}
void combine(){
if (l==NULL) return;
sum=l->sum +r->sum;
mn=min(l->mn,r->mn);
mx=max(l->mx,r->mx);
}
#define UPDATE(name)\
void name(int x, int y, int v){\
if (s==x&&e==y) {self_##name(v); return;}\
int m=(s+e)>>1; \
create_children(); lazy();\
if (x<=m) l->name(x,min(y,m),v);\
if (y>m) r->name(max(x,m+1),y,v);\
combine();\
}
UPDATE(add)
UPDATE(set)
#define QUERY(name,fn,var,lazyfn)\
int range_##name(int x, int y){\
if (s==x&&e==y) return var;\
if (l==NULL||lset) return lazyfn(var);\
int m=(s+e)>>1; lazy();\
if (y<=m) return l->range_##name(x,y);\
if (x>m) return r->range_##name(x,y);\
return fn(l->range_##name(x,m), r->range_##name(m+1,y));\
}
#define SAME(var) (var)
#define PART(var) ((var)/(e-s+1)*(y-x+1))
#define SUM(a,b) ((a)+(b))
QUERY(min,min,mn,SAME)
QUERY(max,max,mx,SAME)
QUERY(sum,SUM,sum,PART)
~node(){
if (l!=NULL) delete l;
if (r!=NULL) delete r;
}
}*root;
int32_t main(){
int N,K,Q;
cin>>N>>K>>Q;
int X[N+5],T[N+5],A[N+5],B[N+5];
for (int i=0; i<N; i++){
cin>>X[i]>>T[i]>>A[i]>>B[i];
}
while (Q--){
int L, Y; cin>>L>>Y;
root = new node(1,K+1);
root->set(1,K+1,-1);
for (int i=0; i<N; i++){
if (A[i]<=Y && B[i]>=Y){
int curr_ina = root->range_max(T[i],T[i]);
if (curr_ina==-1) root->set(T[i],T[i],abs(X[i]-L));
else{
root->set(T[i],T[i],min(curr_ina, abs(X[i]-L)));
}
}
}
if (root->range_min(1,K)==-1) cout<<"-1";
else cout<<root->range_max(1,K);
//for (int i=1; i<=K; i++) cout<<root->range_min(i,i)<<" ";
cout<<"\n";
}
}
Compilation message (stderr)
new_home.cpp: In constructor 'node::node(long long int, long long int, long long int*)':
new_home.cpp:14:7: warning: 'node::lset' will be initialized after [-Wreorder]
14 | bool lset;
| ^~~~
new_home.cpp:13:16: warning: 'long long int node::add_val' [-Wreorder]
13 | int mn,mx,sum,add_val,set_val;
| ^~~~~~~
new_home.cpp:16:2: warning: when initialized here [-Wreorder]
16 | node (int _s, int _e, int A[]=NULL): s(_s), e(_e), mn(0), mx(0), sum(0), lset(0), add_val(0), set_val(0), l(NULL), r(NULL){
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |