#include <bits/stdc++.h>
#define int long long
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 3e5 + 5;
int le[N], ri[N];
struct Node {
int st, en, len, cost;
//We start at [st....st + len], and ends at [en...en + len]
Node(int st = -1, int en = -1, int len = 0, int cost = 0): st(st), en(en), len(len), cost(cost) {};
int get(int x, int y) {
int ans = cost;
if (x < st) x = st;
if (x > st + len) {
// cout << "x = " << x << " st + len = " << st + len << "\n";
ans += (x - st - len);
x = st + len;
}
x += (en - st);
if (y < x) ans += (x - y);
return ans;
}
};
Node operator+(Node lhs, Node rhs) {
if (lhs.st == -1) return rhs;
if (rhs.st == -1) return lhs;
//2 sections does not intersect
if (lhs.en + lhs.len < rhs.st) {
return Node(lhs.st + lhs.len, rhs.en, 0, lhs.cost + rhs.cost);
} else if (rhs.st + rhs.len < lhs.en) {
return Node(lhs.st, rhs.en + rhs.len, 0, lhs.cost + rhs.cost + (lhs.en - rhs.st - rhs.len));
} else {
//2 sections [lhs.en...lhs.en + lhs.len] and [rhs.st....rhs.st + rhs.len] do intersect.
int l = max(lhs.en, rhs.st), r = min(lhs.en + lhs.len, rhs.st + rhs.len);
int diffl = lhs.en - lhs.st, diffr = rhs.en - rhs.st;
return Node(l - diffl, l + diffr, r - l, lhs.cost + rhs.cost);
}
}
class SegTree {
private:
Node t[N << 2];
void build(int l, int r, int x) {
if (l == r) {
if (!rev) t[x] = Node(le[l], le[l] + 1, ri[l] - le[l], 0);
else t[x] = Node(le[n - 1 - l], le[n - 1 - l] + 1, ri[n - 1 - l] - le[n - 1 - l], 0);
// cout << "t[" << l << "->" << r << "].st = " << t[x].st << " en = " << t[x].en << " len = " << t[x].len << "\n";
return;
}
int m = (l + r) >> 1;
build(l, m, x << 1), build(m + 1, r, x << 1 | 1);
t[x] = t[x << 1] + t[x << 1 | 1];
// cout << "t[" << l << "->" << r << "].st = " << t[x].st << " en = " << t[x].en << " len = " << t[x].len << "\n";
}
void upd(int l, int r, int pos, int x) {
if (l == r) {
if (!rev) t[x] = Node(le[l], le[l] + 1, ri[l] - le[l], 0);
else t[x] = Node(le[n - 1 - l], le[n - 1 - l] + 1, ri[n - 1 - l] - le[n - 1 - l], 0);
return;
}
int m = (l + r) >> 1;
if (pos <= m) upd(l, m, pos, x << 1);
else upd(m + 1, r, pos, x << 1 | 1);
t[x] = t[x << 1] + t[x << 1 | 1];
// cout << "t[" << x << "].st = " << t[x].st << "\n";
}
Node get(int l, int r, int s, int e, int x) {
if (l > e || r < s) return Node();
if (s <= l && r <= e) return t[x];
int m = (l + r) >> 1;
return get(l, m, s, e, x << 1) + get(m + 1, r, s, e, x << 1 | 1);
}
public:
int n;
bool rev;
void init(int _n, bool _rev) {
n = _n;
rev = _rev;
build(0, n - 1, 1);
}
void upd(int pos) {
assert(pos >= 0 && pos < n);
if (!rev) upd(0, n - 1, pos, 1);
else upd(0, n - 1, n - 1 - pos, 1);
}
int get(int a, int b, int x, int y) {
// cout << "a = " << a << " b = " << b << "\n";
assert(a >= 0 && b >= 0 && a < n && b - 1 < n);
Node ans = get(0, n - 1, a, b - 1, 1);
// cout << ans.st << " " << ans.en << " " << ans.len << " cost = " << ans.cost << "\n";
return ans.get(x, y);
}
} st, st2;
int n, q;
signed main() {
#ifdef BLU
in("blu.inp");
#endif
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
assert(0);
cin >> n >> q;
fw (i, 0, n - 1) {
cin >> le[i] >> ri[i];
ri[i]--;
}
// We want to go from city A to B, there is some segment of time that allows us to spend the minimum cost.
// Everything outside the range can be moved into the range and spend the aforementioned cost.
st.init(n - 1, 0);
// cout << "Revtree\n";
st2.init(n - 1, 1);
while (q--) {
int type;
cin >> type;
if (type == 1) {
int p, s, e;
cin >> p >> s >> e;
p--;
le[p] = s, ri[p] = e - 1;
st.upd(p);
st2.upd(p);
} else {
int a, b, x, y;
cin >> a >> x >> b >> y;
if (a == b) {
if (y < x) cout << x - y << "\n";
else cout << "0\n";
continue;
}
if (a < b) {
a--, b--;
cout << st.get(a, b, x, y) << "\n";
} else {
a--, b--;
a = n - 1 - a, b = n - 1 - b;
cout << st2.get(a, b, x, y) << "\n";
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
122 ms |
152700 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
124 ms |
152828 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
122 ms |
152700 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
