#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
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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
2 ms |
620 KB |
Output is correct |
12 |
Correct |
2 ms |
620 KB |
Output is correct |
13 |
Correct |
3 ms |
620 KB |
Output is correct |
14 |
Correct |
2 ms |
620 KB |
Output is correct |
15 |
Correct |
2 ms |
620 KB |
Output is correct |
16 |
Correct |
2 ms |
620 KB |
Output is correct |
17 |
Correct |
2 ms |
620 KB |
Output is correct |
18 |
Correct |
2 ms |
620 KB |
Output is correct |
19 |
Correct |
2 ms |
620 KB |
Output is correct |
20 |
Correct |
2 ms |
620 KB |
Output is correct |
21 |
Correct |
2 ms |
620 KB |
Output is correct |
22 |
Correct |
2 ms |
620 KB |
Output is correct |
23 |
Correct |
2 ms |
620 KB |
Output is correct |
24 |
Correct |
2 ms |
620 KB |
Output is correct |
25 |
Correct |
2 ms |
620 KB |
Output is correct |
26 |
Correct |
2 ms |
620 KB |
Output is correct |
27 |
Correct |
2 ms |
620 KB |
Output is correct |
28 |
Correct |
2 ms |
620 KB |
Output is correct |
29 |
Correct |
2 ms |
620 KB |
Output is correct |
30 |
Correct |
2 ms |
748 KB |
Output is correct |
31 |
Correct |
2 ms |
620 KB |
Output is correct |
32 |
Correct |
2 ms |
620 KB |
Output is correct |
33 |
Correct |
2 ms |
620 KB |
Output is correct |
34 |
Correct |
2 ms |
620 KB |
Output is correct |
35 |
Correct |
2 ms |
620 KB |
Output is correct |
36 |
Correct |
2 ms |
620 KB |
Output is correct |
37 |
Correct |
2 ms |
620 KB |
Output is correct |
38 |
Correct |
2 ms |
620 KB |
Output is correct |
39 |
Correct |
2 ms |
620 KB |
Output is correct |
40 |
Correct |
2 ms |
620 KB |
Output is correct |
41 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
937 ms |
84572 KB |
Output is correct |
2 |
Correct |
906 ms |
80540 KB |
Output is correct |
3 |
Correct |
910 ms |
81356 KB |
Output is correct |
4 |
Correct |
889 ms |
79084 KB |
Output is correct |
5 |
Correct |
908 ms |
84332 KB |
Output is correct |
6 |
Correct |
894 ms |
83180 KB |
Output is correct |
7 |
Correct |
936 ms |
85484 KB |
Output is correct |
8 |
Correct |
921 ms |
89068 KB |
Output is correct |
9 |
Correct |
886 ms |
79852 KB |
Output is correct |
10 |
Correct |
911 ms |
85228 KB |
Output is correct |
11 |
Correct |
981 ms |
84592 KB |
Output is correct |
12 |
Correct |
940 ms |
89964 KB |
Output is correct |
13 |
Correct |
932 ms |
91116 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
2 ms |
620 KB |
Output is correct |
12 |
Correct |
2 ms |
620 KB |
Output is correct |
13 |
Correct |
3 ms |
620 KB |
Output is correct |
14 |
Correct |
2 ms |
620 KB |
Output is correct |
15 |
Correct |
2 ms |
620 KB |
Output is correct |
16 |
Correct |
2 ms |
620 KB |
Output is correct |
17 |
Correct |
2 ms |
620 KB |
Output is correct |
18 |
Correct |
2 ms |
620 KB |
Output is correct |
19 |
Correct |
2 ms |
620 KB |
Output is correct |
20 |
Correct |
2 ms |
620 KB |
Output is correct |
21 |
Correct |
2 ms |
620 KB |
Output is correct |
22 |
Correct |
2 ms |
620 KB |
Output is correct |
23 |
Correct |
2 ms |
620 KB |
Output is correct |
24 |
Correct |
2 ms |
620 KB |
Output is correct |
25 |
Correct |
2 ms |
620 KB |
Output is correct |
26 |
Correct |
2 ms |
620 KB |
Output is correct |
27 |
Correct |
2 ms |
620 KB |
Output is correct |
28 |
Correct |
2 ms |
620 KB |
Output is correct |
29 |
Correct |
2 ms |
620 KB |
Output is correct |
30 |
Correct |
2 ms |
748 KB |
Output is correct |
31 |
Correct |
2 ms |
620 KB |
Output is correct |
32 |
Correct |
2 ms |
620 KB |
Output is correct |
33 |
Correct |
2 ms |
620 KB |
Output is correct |
34 |
Correct |
2 ms |
620 KB |
Output is correct |
35 |
Correct |
2 ms |
620 KB |
Output is correct |
36 |
Correct |
2 ms |
620 KB |
Output is correct |
37 |
Correct |
2 ms |
620 KB |
Output is correct |
38 |
Correct |
2 ms |
620 KB |
Output is correct |
39 |
Correct |
2 ms |
620 KB |
Output is correct |
40 |
Correct |
2 ms |
620 KB |
Output is correct |
41 |
Correct |
1 ms |
364 KB |
Output is correct |
42 |
Correct |
937 ms |
84572 KB |
Output is correct |
43 |
Correct |
906 ms |
80540 KB |
Output is correct |
44 |
Correct |
910 ms |
81356 KB |
Output is correct |
45 |
Correct |
889 ms |
79084 KB |
Output is correct |
46 |
Correct |
908 ms |
84332 KB |
Output is correct |
47 |
Correct |
894 ms |
83180 KB |
Output is correct |
48 |
Correct |
936 ms |
85484 KB |
Output is correct |
49 |
Correct |
921 ms |
89068 KB |
Output is correct |
50 |
Correct |
886 ms |
79852 KB |
Output is correct |
51 |
Correct |
911 ms |
85228 KB |
Output is correct |
52 |
Correct |
981 ms |
84592 KB |
Output is correct |
53 |
Correct |
940 ms |
89964 KB |
Output is correct |
54 |
Correct |
932 ms |
91116 KB |
Output is correct |
55 |
Correct |
1 ms |
364 KB |
Output is correct |
56 |
Correct |
867 ms |
80652 KB |
Output is correct |
57 |
Correct |
843 ms |
75756 KB |
Output is correct |
58 |
Correct |
874 ms |
82924 KB |
Output is correct |
59 |
Correct |
867 ms |
83436 KB |
Output is correct |
60 |
Correct |
847 ms |
77808 KB |
Output is correct |
61 |
Correct |
882 ms |
85816 KB |
Output is correct |
62 |
Correct |
874 ms |
85308 KB |
Output is correct |
63 |
Correct |
884 ms |
85176 KB |
Output is correct |
64 |
Correct |
900 ms |
85852 KB |
Output is correct |
65 |
Correct |
870 ms |
81728 KB |
Output is correct |
66 |
Correct |
876 ms |
82192 KB |
Output is correct |
67 |
Correct |
908 ms |
85380 KB |
Output is correct |
68 |
Correct |
875 ms |
78772 KB |
Output is correct |
69 |
Correct |
915 ms |
87660 KB |
Output is correct |
70 |
Correct |
864 ms |
78320 KB |
Output is correct |
71 |
Correct |
840 ms |
75252 KB |
Output is correct |
72 |
Correct |
852 ms |
78148 KB |
Output is correct |
73 |
Correct |
873 ms |
85680 KB |
Output is correct |
74 |
Correct |
881 ms |
86048 KB |
Output is correct |
75 |
Correct |
886 ms |
87240 KB |
Output is correct |
76 |
Correct |
889 ms |
88108 KB |
Output is correct |
77 |
Correct |
1 ms |
364 KB |
Output is correct |