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
struct val{
int a,b,c,d;
val(){}
val(int _a, int _b, int _c, int _d){
a = _a; b = _b; c = _c; d = _d;
}
int func(int S, int E){
return max(max(0LL,S-a)+max(0LL,b-E)+d,d+max(0LL,S-E+c));
}
};
val mer(val a, val b){
val c = val(0,0,0,0);
c.d = a.func(0,b.a) + b.func(b.a,1100000000LL);
c.a = 1100000000LL-(a.func(1100000000LL,b.a) + b.func(b.a,1100000000LL) - c.d);
c.b = a.func(0,a.b) + b.func(a.b,0)-c.d;
if (c.d>0) c.c = -99999999999999999LL;
else c.c = a.c+b.c;
return c;
}
int L[300005];
int R[300005];
struct node{
int s,e;
val v,v2;
node *l,*r;
node (int _s, int _e){
s = _s; e = _e;
if (s==e){
v = val(R[s]-1,L[s]+1,1,0);
v2 = val(R[s]-1,L[s]+1,1,0);
}
else{
l = new node(s,(s+e)/2);
r = new node((s+e)/2+1,e);
v = mer(l->v,r->v);
v2 = mer(r->v2,l->v2);
}
}
void upd(int pos){
if (s==e){
v = val(R[s]-1,L[s]+1,1,0);
v2 = val(R[s]-1,L[s]+1,1,0);
}
else{
if (pos<=(s+e)/2){
l->upd(pos);
}
else{
r->upd(pos);
}
v = mer(l->v,r->v);
v2 = mer(r->v2,l->v2);
}
}
val qu(int a, int b, bool rev){
if (a<=s && e<=b){
return rev?v2:v;
}
if (b<=(s+e)/2){
return l->qu(a,b,rev);
}
if (a>(s+e)/2){
return r->qu(a,b,rev);
}
return rev?mer(r->qu(a,b,rev),l->qu(a,b,rev)):mer(l->qu(a,b,rev),r->qu(a,b,rev));
}
}*root;
int32_t main(){
int n,q;
scanf("%lld%lld",&n,&q);
for (int x = 0; x<n-1; x++){
scanf("%lld%lld",&L[x],&R[x]);
}
root = new node(0,n-1);
for (int x = 0; x<q; x++){
int t;
scanf("%lld",&t);
if (t==1){
int a,b,c;
scanf("%lld%lld%lld",&a,&b,&c);
a--;
L[a] = b;
R[a] = c;
root->upd(a);
}
else{
int a,b,c,d;
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
a--;c--;
if (a==c){
printf("%lld\n",max(0LL,b-d));
}
else{
printf("%lld\n",root->qu(min(a,c),max(a,c)-1,c<a).func(b,d));
}
}
}
}
Compilation message (stderr)
timeleap.cpp: In function 'int32_t main()':
timeleap.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
79 | scanf("%lld%lld",&n,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~
timeleap.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
81 | scanf("%lld%lld",&L[x],&R[x]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
86 | scanf("%lld",&t);
| ~~~~~^~~~~~~~~~~
timeleap.cpp:89:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
89 | scanf("%lld%lld%lld",&a,&b,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
97 | scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |