#include <cstdio>
#include <cstring>
#include <algorithm>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef pair < int, int > pii;
typedef long long ll;
const int OFF = (1 << 19);
const int INF = 0x3f3f3f3f;
struct node{
int f_t1, f_t2, c_t;
int c_p, nula;
ll f_p;
node(){
f_t1 = 0, f_t2 = INF, c_t = 0;
c_p = INF, f_p = 0; nula = 0;
}
node(int s, int t){
f_t1 = s + 1, f_t2 = t, c_t = s;
f_p = 0, c_p = t - 1; nula = 0;
}
int get_time(int s_t){
return min(f_t2, f_t1 + max(0, s_t - c_t));
}
ll get_price(int s_t){
return f_p + max(s_t - c_p, 0);
}
void print(){
printf("- - -\n");
printf("f_t1 = %d f_t2 = %d\n", f_t1, f_t2);
printf("c_t = %d\n", c_t);
printf("f_p = %lld c_p = %d\n", f_p, c_p);
printf("nula = %d\n", nula);
}
};
node NULA, T[2 * OFF][2];
node operator+(node A, node B){
if(A.nula) return B;
if(B.nula) return A;
node C;
C.f_t1 = B.get_time(A.f_t1);
C.f_t2 = B.get_time(A.f_t2);
C.c_t = A.c_t;
if(A.f_t1 < B.c_t){
if(A.f_t2 >= B.c_t)
C.c_t += B.c_t - A.f_t1;
else
C.c_t = INF;
}
C.c_p = A.c_p;
C.f_p = A.f_p + B.get_price(A.f_t1);
if(A.get_time(A.c_p) > B.c_p && A.f_t1 <= B.c_p){
C.c_p = A.c_p - (A.get_time(A.c_p) - B.c_p);
}
if(A.f_t1 > B.c_p)
C.c_p = min(C.c_p, A.c_t);
return C;
}
node query(int i, int a, int b, int lo, int hi, bool rev){
if(lo <= a && b <= hi) return T[i][rev];
if(a > hi || b < lo) return NULA;
if(!rev)
return query(2 * i, a, (a + b) / 2, lo, hi, rev) + query(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, rev);
else
return query(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, rev) + query(2 * i, a, (a + b) / 2, lo, hi, rev);
}
void update(int i, int s, int t){
T[OFF + i][0] = node(s, t);
T[OFF + i][1] = node(s, t);
for(i = (OFF + i) / 2 ; i ; i /= 2){
T[i][0] = T[2 * i][0] + T[2 * i + 1][0];
T[i][1] = T[2 * i + 1][1] + T[2 * i][1];
}
}
int n, q;
int main(){
NULA.nula = 1;
for(int i = 0;i < 2 * OFF;i++)
T[i][0] = NULA, T[i][1] = NULA;
scanf("%d%d", &n, &q);
for(int i = 1;i < n;i++){
int x, y; scanf("%d%d", &x, &y);
update(i, x, y);
}
for(int i = 0;i < q;i++){
int ty; scanf("%d", &ty);
if(ty == 1){
int p, x, y; scanf("%d%d%d", &p, &x, &y);
update(p, x, y);
}
else{
int l, l_t, r, r_t; scanf("%d%d%d%d", &l,&l_t, &r, &r_t);
node ret = NULA;
if(l < r)
ret = query(1, 0, OFF - 1, l, r - 1, 0);
if(l > r)
ret = query(1, 0, OFF - 1, r, l - 1, 1);
//ret.print();
ll ans = ret.get_price(l_t) + max(0, ret.get_time(l_t) - r_t);
printf("%lld\n", ans);
}
}
return 0;
}
Compilation message
timeleap.cpp: In function 'int main()':
timeleap.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
93 | scanf("%d%d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~
timeleap.cpp:95:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
95 | int x, y; scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
timeleap.cpp:99:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
99 | int ty; scanf("%d", &ty);
| ~~~~~^~~~~~~~~~~
timeleap.cpp:101:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
101 | int p, x, y; scanf("%d%d%d", &p, &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:105:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
105 | int l, l_t, r, r_t; scanf("%d%d%d%d", &l,&l_t, &r, &r_t);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
65912 KB |
Output is correct |
2 |
Correct |
47 ms |
66000 KB |
Output is correct |
3 |
Correct |
54 ms |
65912 KB |
Output is correct |
4 |
Correct |
47 ms |
65916 KB |
Output is correct |
5 |
Correct |
48 ms |
66044 KB |
Output is correct |
6 |
Correct |
46 ms |
65912 KB |
Output is correct |
7 |
Correct |
47 ms |
65912 KB |
Output is correct |
8 |
Correct |
52 ms |
66168 KB |
Output is correct |
9 |
Correct |
47 ms |
65912 KB |
Output is correct |
10 |
Correct |
47 ms |
65920 KB |
Output is correct |
11 |
Correct |
57 ms |
65912 KB |
Output is correct |
12 |
Correct |
50 ms |
66040 KB |
Output is correct |
13 |
Correct |
54 ms |
66040 KB |
Output is correct |
14 |
Correct |
51 ms |
66040 KB |
Output is correct |
15 |
Correct |
51 ms |
66044 KB |
Output is correct |
16 |
Correct |
54 ms |
66040 KB |
Output is correct |
17 |
Correct |
50 ms |
66040 KB |
Output is correct |
18 |
Correct |
50 ms |
66040 KB |
Output is correct |
19 |
Correct |
54 ms |
66040 KB |
Output is correct |
20 |
Correct |
49 ms |
66048 KB |
Output is correct |
21 |
Correct |
49 ms |
66040 KB |
Output is correct |
22 |
Correct |
53 ms |
66040 KB |
Output is correct |
23 |
Correct |
49 ms |
66040 KB |
Output is correct |
24 |
Correct |
49 ms |
66040 KB |
Output is correct |
25 |
Correct |
50 ms |
66040 KB |
Output is correct |
26 |
Correct |
49 ms |
66040 KB |
Output is correct |
27 |
Correct |
51 ms |
66020 KB |
Output is correct |
28 |
Correct |
49 ms |
66040 KB |
Output is correct |
29 |
Correct |
50 ms |
66040 KB |
Output is correct |
30 |
Correct |
50 ms |
66040 KB |
Output is correct |
31 |
Correct |
49 ms |
66040 KB |
Output is correct |
32 |
Correct |
49 ms |
66016 KB |
Output is correct |
33 |
Correct |
49 ms |
66040 KB |
Output is correct |
34 |
Correct |
50 ms |
66040 KB |
Output is correct |
35 |
Correct |
49 ms |
66040 KB |
Output is correct |
36 |
Correct |
49 ms |
66040 KB |
Output is correct |
37 |
Correct |
49 ms |
66040 KB |
Output is correct |
38 |
Correct |
49 ms |
66040 KB |
Output is correct |
39 |
Correct |
49 ms |
66040 KB |
Output is correct |
40 |
Correct |
50 ms |
66040 KB |
Output is correct |
41 |
Correct |
47 ms |
65912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1109 ms |
70296 KB |
Output is correct |
2 |
Correct |
1086 ms |
85480 KB |
Output is correct |
3 |
Correct |
1126 ms |
85592 KB |
Output is correct |
4 |
Correct |
1167 ms |
85448 KB |
Output is correct |
5 |
Correct |
1115 ms |
85860 KB |
Output is correct |
6 |
Correct |
1115 ms |
85624 KB |
Output is correct |
7 |
Correct |
1123 ms |
85768 KB |
Output is correct |
8 |
Correct |
1122 ms |
86408 KB |
Output is correct |
9 |
Correct |
1077 ms |
85752 KB |
Output is correct |
10 |
Correct |
1154 ms |
85872 KB |
Output is correct |
11 |
Correct |
1102 ms |
85812 KB |
Output is correct |
12 |
Correct |
1121 ms |
86392 KB |
Output is correct |
13 |
Correct |
1138 ms |
86392 KB |
Output is correct |
14 |
Correct |
46 ms |
65912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
65912 KB |
Output is correct |
2 |
Correct |
47 ms |
66000 KB |
Output is correct |
3 |
Correct |
54 ms |
65912 KB |
Output is correct |
4 |
Correct |
47 ms |
65916 KB |
Output is correct |
5 |
Correct |
48 ms |
66044 KB |
Output is correct |
6 |
Correct |
46 ms |
65912 KB |
Output is correct |
7 |
Correct |
47 ms |
65912 KB |
Output is correct |
8 |
Correct |
52 ms |
66168 KB |
Output is correct |
9 |
Correct |
47 ms |
65912 KB |
Output is correct |
10 |
Correct |
47 ms |
65920 KB |
Output is correct |
11 |
Correct |
57 ms |
65912 KB |
Output is correct |
12 |
Correct |
50 ms |
66040 KB |
Output is correct |
13 |
Correct |
54 ms |
66040 KB |
Output is correct |
14 |
Correct |
51 ms |
66040 KB |
Output is correct |
15 |
Correct |
51 ms |
66044 KB |
Output is correct |
16 |
Correct |
54 ms |
66040 KB |
Output is correct |
17 |
Correct |
50 ms |
66040 KB |
Output is correct |
18 |
Correct |
50 ms |
66040 KB |
Output is correct |
19 |
Correct |
54 ms |
66040 KB |
Output is correct |
20 |
Correct |
49 ms |
66048 KB |
Output is correct |
21 |
Correct |
49 ms |
66040 KB |
Output is correct |
22 |
Correct |
53 ms |
66040 KB |
Output is correct |
23 |
Correct |
49 ms |
66040 KB |
Output is correct |
24 |
Correct |
49 ms |
66040 KB |
Output is correct |
25 |
Correct |
50 ms |
66040 KB |
Output is correct |
26 |
Correct |
49 ms |
66040 KB |
Output is correct |
27 |
Correct |
51 ms |
66020 KB |
Output is correct |
28 |
Correct |
49 ms |
66040 KB |
Output is correct |
29 |
Correct |
50 ms |
66040 KB |
Output is correct |
30 |
Correct |
50 ms |
66040 KB |
Output is correct |
31 |
Correct |
49 ms |
66040 KB |
Output is correct |
32 |
Correct |
49 ms |
66016 KB |
Output is correct |
33 |
Correct |
49 ms |
66040 KB |
Output is correct |
34 |
Correct |
50 ms |
66040 KB |
Output is correct |
35 |
Correct |
49 ms |
66040 KB |
Output is correct |
36 |
Correct |
49 ms |
66040 KB |
Output is correct |
37 |
Correct |
49 ms |
66040 KB |
Output is correct |
38 |
Correct |
49 ms |
66040 KB |
Output is correct |
39 |
Correct |
49 ms |
66040 KB |
Output is correct |
40 |
Correct |
50 ms |
66040 KB |
Output is correct |
41 |
Correct |
47 ms |
65912 KB |
Output is correct |
42 |
Correct |
1109 ms |
70296 KB |
Output is correct |
43 |
Correct |
1086 ms |
85480 KB |
Output is correct |
44 |
Correct |
1126 ms |
85592 KB |
Output is correct |
45 |
Correct |
1167 ms |
85448 KB |
Output is correct |
46 |
Correct |
1115 ms |
85860 KB |
Output is correct |
47 |
Correct |
1115 ms |
85624 KB |
Output is correct |
48 |
Correct |
1123 ms |
85768 KB |
Output is correct |
49 |
Correct |
1122 ms |
86408 KB |
Output is correct |
50 |
Correct |
1077 ms |
85752 KB |
Output is correct |
51 |
Correct |
1154 ms |
85872 KB |
Output is correct |
52 |
Correct |
1102 ms |
85812 KB |
Output is correct |
53 |
Correct |
1121 ms |
86392 KB |
Output is correct |
54 |
Correct |
1138 ms |
86392 KB |
Output is correct |
55 |
Correct |
46 ms |
65912 KB |
Output is correct |
56 |
Correct |
1018 ms |
82828 KB |
Output is correct |
57 |
Correct |
979 ms |
82260 KB |
Output is correct |
58 |
Correct |
1061 ms |
83032 KB |
Output is correct |
59 |
Correct |
1068 ms |
82900 KB |
Output is correct |
60 |
Correct |
1010 ms |
82588 KB |
Output is correct |
61 |
Correct |
1026 ms |
82980 KB |
Output is correct |
62 |
Correct |
1049 ms |
83064 KB |
Output is correct |
63 |
Correct |
1086 ms |
82904 KB |
Output is correct |
64 |
Correct |
1037 ms |
83008 KB |
Output is correct |
65 |
Correct |
1045 ms |
82768 KB |
Output is correct |
66 |
Correct |
1041 ms |
82680 KB |
Output is correct |
67 |
Correct |
1071 ms |
82936 KB |
Output is correct |
68 |
Correct |
984 ms |
82268 KB |
Output is correct |
69 |
Correct |
1020 ms |
83204 KB |
Output is correct |
70 |
Correct |
964 ms |
82552 KB |
Output is correct |
71 |
Correct |
973 ms |
81652 KB |
Output is correct |
72 |
Correct |
977 ms |
82128 KB |
Output is correct |
73 |
Correct |
1055 ms |
82552 KB |
Output is correct |
74 |
Correct |
1076 ms |
82504 KB |
Output is correct |
75 |
Correct |
1034 ms |
82612 KB |
Output is correct |
76 |
Correct |
1035 ms |
83320 KB |
Output is correct |
77 |
Correct |
47 ms |
65920 KB |
Output is correct |