#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pll;
struct node{
ll t, l, r, x1, x2, v;
node() {}
node(ll l, ll r) : t(1), l(l), r(r) {}
node(ll l, ll r, ll x) : t(2), l(l), r(r), x1(x), x2(x), v(0) {}
pll pass(ll x)
{
if(t == 1){
if(l <= x && x <= r) return pll(x, 0);
else if(x < l) return pll(l, 0);
else return pll(r, x - r);
}
else{
ll _v = v;
if(x < l) x = l;
else if(r < x) _v += x - r, x = r;
if(x > x1) _v += x - x1;
return pll(x2, _v);
}
}
node operator + (node n)
{
if(t == 1 && n.t == 1){
if(max(l, n.l) <= min(r, n.r)){
return node(max(l, n.l), min(r, n.r));
}
else if(r < n.l) return node(l, r, n.l);
else return node(l, r, n.r);
}
else if(t == 1 && n.t == 2){
node ret = n;
if(max(l, n.l) <= min(r, n.r)){
ret.l = max(l, n.l);
ret.r = min(r, n.r);
}
else if(r < n.l){
ret.x1 = n.l;
if(n.l > n.x1) ret.v += n.l - n.x1;
}
else{
ret.x1 = n.r;
if(n.r > n.x1) ret.v += n.r - n.x1;
}
return ret;
}
else if(t == 2 && n.t == 1){
node ret(l, r, x1);
ret.v = v;
if(n.l <= x2 && x2 <= n.r) ret.x2 = x2;
else if(x2 < n.l) ret.x2 = n.l;
else if(n.r < x2) ret.x2 = n.r, ret.v += x2 - n.r;
return ret;
}
else{
node ret(l, r, x1);
ll _x2, _v;
tie(_x2, _v) = n.pass(x2);
ret.x2 = _x2; ret.v = v + _v;
return ret;
}
}
void print()
{
if(t == 1) printf("type 1 : %lld %lld\n", l, r);
else printf("type 2 : %lld %lld -> %lld -> (%lld) -> %lld\n", l, r, x1, v, x2);
}
};
node T1[1101010], T2[1101010];
ll n, sz;
bool test(ll x, node n1, node n2)
{
node n3 = n1 + n2;
ll x1, v1, x2, v2, _v;
tie(x1, v1) = n3.pass(x);
tie(x2, _v) = n1.pass(x);
tie(x2, v2) = n2.pass(x2);
v2 += _v;
if(x1 != x2) return 1;
if(v1 != v2) return 1;
return 0;
}
void update(node *T, ll p)
{
p = p + sz >> 1;
for(; p; p>>=1){
if(test(T[p << 1].l, T[p << 1], T[p << 1 | 1])) 1 / 0;
if(test(T[p << 1].r, T[p << 1], T[p << 1 | 1])) 1 / 0;
T[p] = T[p << 1] + T[p << 1 | 1];
}
}
node get_sum(node *T, ll l, ll r)
{
node sl, sr;
ll fl = 0, fr = 0;
l += sz; r += sz;
for(; l<r; ){
if(l & 1){
if(!fl) sl = T[l], fl = 1;
else sl = sl + T[l];
}
if(~r & 1){
if(!fr) sr = T[r], fr = 1;
else sr = T[r] + sr;
}
l = l + 1 >> 1;
r = r - 1 >> 1;
}
if(l == r){
if(!fl) sl = T[l], fl = 1;
else sl = sl + T[l];
}
if(!fl) return sr;
else if(!fr) return sl;
else return sl + sr;
}
/*
node get_sum(node *T, ll l, ll r)
{
node ret = T[sz + l];
ll i;
for(i=l+1; i<=r; i++){
ret = ret + T[sz + i];
}
return ret;
}
*/
int main()
{
ll q, i, t, l, r, x, y, z, s, e, v;
scanf("%lld%lld", &n, &q);
for(sz=1; sz<=n; sz<<=1);
for(i=0; i<sz; i++){
T1[sz + i] = node(1, 0, 0);
T2[sz + i] = node(1, 0, 0);
}
for(i=1; i<n; i++){
scanf("%lld%lld", &l, &r);
T1[sz + i] = node(l - i, r - i - 1);
T2[sz + n - i] = node(l - n + i, r - n + i - 1);
}
/* for(i=1; i<n-2; i++){
printf("%lld %lld %lld\n", i, i + 1, i + 2);
(T1[sz + i] + (T1[sz + i + 1] + T1[sz + i + 2])).print();
((T1[sz + i] + T1[sz + i + 1]) + T1[sz + i + 2]).print();
}
*/
for(i=sz-1; i>=1; i--){
T1[i] = T1[i << 1] + T1[i << 1 | 1];
T2[i] = T2[i << 1] + T2[i << 1 | 1];
}
for(; q--; ){
scanf("%lld", &t);
if(t == 1){
scanf("%lld%lld%lld", &i, &l, &r);
T1[sz + i] = node(l - i, r - i - 1);
T2[sz + n - i] = node(l - n + i, r - n + i - 1);
update(T1, i); update(T2, n - i);
}
else{
scanf("%lld%lld%lld%lld", &s, &x, &e, &y);
if(s == e) printf("%lld\n", max(0ll, x - y));
else if(s < e){
x -= s; y -= e;
tie(z, v) = get_sum(T1, s, e - 1).pass(x);
printf("%lld\n", v + max(0ll, z - y));
}
else{
s = n - s + 1; e = n - e + 1;
x -= s; y -= e;
tie(z, v) = get_sum(T2, s, e - 1).pass(x);
printf("%lld\n", v + max(0ll, z - y));
}
}
}
return 0;
}
Compilation message
timeleap.cpp: In function 'void update(node*, ll)':
timeleap.cpp:106:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
p = p + sz >> 1;
~~^~~~
timeleap.cpp:108:53: warning: division by zero [-Wdiv-by-zero]
if(test(T[p << 1].l, T[p << 1], T[p << 1 | 1])) 1 / 0;
~~^~~
timeleap.cpp:108:53: warning: statement has no effect [-Wunused-value]
timeleap.cpp:109:53: warning: division by zero [-Wdiv-by-zero]
if(test(T[p << 1].r, T[p << 1], T[p << 1 | 1])) 1 / 0;
~~^~~
timeleap.cpp:109:53: warning: statement has no effect [-Wunused-value]
timeleap.cpp: In function 'node get_sum(node*, ll, ll)':
timeleap.cpp:130:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
l = l + 1 >> 1;
~~^~~
timeleap.cpp:131:9: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
r = r - 1 >> 1;
~~^~~
timeleap.cpp: In function 'int main()':
timeleap.cpp:159:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &n, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~
timeleap.cpp:169:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &l, &r);
~~~~~^~~~~~~~~~~~~~~~~~~~
timeleap.cpp:186:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &t);
~~~~~^~~~~~~~~~~~
timeleap.cpp:188:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld", &i, &l, &r);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:194:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld%lld", &s, &x, &e, &y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
592 ms |
103428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
