#include "bits/stdc++.h"
using namespace std;
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif
using ll = long long;
#define int ll
struct statt {
int lb, rb, time_wait, power_used;
};
statt comb(statt lc, statt rc) {
statt res;
int delta = lc.time_wait - lc.power_used;
int newl = lc.lb + delta, newr = lc.rb + delta;
res.time_wait = lc.time_wait + rc.time_wait;
res.power_used = lc.power_used + rc.power_used;
if (max(newl, rc.lb) <= min(newr, rc.rb)) {
res.lb = max(newl, rc.lb) - delta;
res.rb = min(newr, rc.rb) - delta;
} else if (newr < rc.lb) {
res.time_wait += (rc.lb - newr);
res.lb = res.rb = lc.rb;
} else {
res.power_used += (newl - rc.rb);
res.lb = res.rb = lc.lb;
}
return res;
}
struct segtree {
statt tree[4 * 200005];
void update(int x, int l, int r, int id, int ul, int ur) {
if (l == r) {
tree[x] = {ul, ur, 0, 0};
return;
}
int mid = (l + r) / 2;
if (id <= mid) update(2 * x, l, mid, id, ul, ur);
else update(2 * x + 1, mid + 1, r, id, ul, ur);
tree[x] = comb(tree[2 * x], tree[2 * x + 1]);
}
statt query(int x, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[x];
if (l > qr || ql > r) return {(int) -2e16, (int) 2e16, 0, 0};
int mid = (l + r) / 2;
return comb(query(2 * x, l, mid, ql, qr), query(2 * x + 1, mid + 1, r, ql, qr));
}
};
segtree seg1, seg2;
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("", "r", stdin);
// freopen("", "w", stdout);
int n, q; cin >> n >> q;
for (int i = 1; i < n; i++) {
int l, r; cin >> l >> r;
int newl= l - i;
int newr = r - (i + 1);
seg1.update(1, 1, n, i, newl, newr);
newl = l - ((n - i));
newr = r - ((n - i) + 1);
seg2.update(1, 1, n, (n - i), newl, newr);
}
while (q--){
int t; cin >> t;
if (t == 1) {
int p, s, e; cin >> p >> s >> e;
int newl = s - p;
int newr = e - (p + 1);
seg1.update(1, 1, n, p, newl, newr);
newl = s - ((n - p));
newr = e - ((n - p) + 1);
seg2.update(1, 1, n, (n - p), newl, newr);
} else {
int a, b, c, d; cin >> a >> b >> c >> d;
if (a < c) {
statt interval = seg1.query(1, 1, n, a, c - 1);
b -= a;
d -= (c);
int start_time = max(b, interval.lb);
if (b > interval.rb) {
interval.power_used += (b - interval.rb);
}
start_time += interval.time_wait;
start_time -= interval.power_used;
if (start_time > d) {
interval.power_used += start_time - d;
}
cout << interval.power_used << "\n";
} else if (a > c) {
statt interval = seg2.query(1, 1, n, n - a + 1, n - c);
b = b - ( n - a + 1);
d = (d) - (n - c );
int start_time = max(b, interval.lb);
if (b > interval.rb) {
interval.power_used += (b - interval.rb);
}
start_time += interval.time_wait;
start_time -= interval.power_used;
if (start_time > d) {
interval.power_used += start_time - d;
}
cout << interval.power_used << "\n";
} else {
if (b < d) {
cout << "0\n";
} else {
cout << b - d << "\n";
}
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
129 ms |
64836 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
