#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){
C.c_t += B.c_t - A.f_t1;
}
C.f_p = B.get_price(A.f_t1);
C.c_p = A.c_p;
if(A.get_time(A.c_p) > B.c_p){
C.c_p = max(A.c_p - (A.get_time(A.c_p) - B.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:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
88 | scanf("%d%d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~
timeleap.cpp:90:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
90 | int x, y; scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
timeleap.cpp:94:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
94 | int ty; scanf("%d", &ty);
| ~~~~~^~~~~~~~~~~
timeleap.cpp:96:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
96 | int p, x, y; scanf("%d%d%d", &p, &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:100:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
100 | 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 |
Incorrect |
46 ms |
65912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1163 ms |
84820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
65912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
