#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 301010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
struct node {
ll down, up, fin, cst;
node() {
down = -INF;
up = INF;
fin = -1;
cst = 0;
}
node(ll down, ll up, ll fin = -1, ll cst = 0) :down(down), up(up), fin(down == up ? down : -1), cst(cst) { }
};
inline node operator+(node n1, node n2) {
int c1, c2;
c1 = n1.down == n1.up;
c2 = n2.down == n2.up;
if (!c1 && !c2) {
if (n1.down >= n2.up) return node(n1.down, n1.down, n2.up, n1.down - n2.up);
if (n1.up <= n2.down) return node(n1.up, n1.up, n2.down, n2.down - n1.up);
return node(max(n1.down, n2.down), min(n1.up, n2.up), -1, 0);
}
if (c1 && !c2) {
node ret;
ret.cst = n1.cst;
ret.up = ret.down = n1.up;
if (n1.fin > n2.up) ret.fin = n2.up, ret.cst += n1.fin - n2.up;
else if (n1.fin < n2.down) ret.fin = n2.down, ret.cst += n2.down - n1.fin;
else ret.fin = n1.fin;
return ret;
}
if (!c1 && c2) {
node ret;
ret.fin = n2.fin;
ret.cst = n2.cst;
if (n1.down > n2.up) ret.up = ret.down = n1.down, ret.cst += n1.down - n2.up;
else if (n1.up < n2.up) ret.up = ret.down = n1.up, ret.cst += n2.up - n1.up;
else ret.up = ret.down = n2.up;
return ret;
}
if (c1 && c2) {
node ret;
ret.up = ret.down = n1.up;
ret.fin = n2.fin;
ret.cst = n1.cst + n2.cst + abs(n1.fin - n2.up);
return ret;
}
}
inline ll get(node n, ll sy, ll ey) {
ll fe;
ll ans = 0;
if (n.up == n.down) fe = n.fin, ans += n.cst + abs(n.up - sy);
else {
if (n.down <= sy && sy <= n.up) fe = sy;
else if (n.down > sy) fe = n.down, ans += n.down - sy;
else fe = n.up, ans += sy - n.up;
}
return ans + abs(ey - fe);
}
node narr[MAX];
namespace segtree {
node tree[MAX * 4];
void init(int s, int e, int loc = 1) {
if (s == e) {
tree[loc] = narr[s];
return;
}
int m = (s + e) >> 1;
init(s, m, loc * 2);
init(m + 1, e, loc * 2 + 1);
tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
}
void upd(int s, int e, int x, node n, int loc = 1) {
if (e < x || x < s) return;
if (s == e) {
tree[loc] = n;
return;
}
int m = (s + e) >> 1;
upd(s, m, x, n, loc * 2);
upd(m + 1, e, x, n, loc * 2 + 1);
tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
}
node query(int s, int e, int l, int r, int loc = 1) {
if (l <= s && e <= r) return tree[loc];
if (e < l || r < s) return node();
int m = (s + e) >> 1;
return query(s, m, l, r, loc * 2) + query(m + 1, e, l, r, loc * 2 + 1);
}
}
int N, M;
ll P[MAX];
ll S[MAX];
ll E[MAX];
vector<int> qv[MAX];
ll A[MAX];
ll B[MAX];
ll C[MAX];
ll D[MAX];
ll qt[MAX];
ll L[MAX];
ll R[MAX];
ll ans[MAX];
void solve() {
int i;
for (i = 1; i <= N; i++) narr[i] = node(L[i] - i, R[i] - i - 1);
segtree::init(1, N - 1);
for (i = 0; i <= M + 1; i++) {
if (1 <= i && i <= M) segtree::upd(1, N - 1, P[i], node(S[i] - P[i], E[i] - P[i] - 1));
for (auto v : qv[i]) {
ans[v] = get(segtree::query(1, N - 1, A[v], C[v] - 1), B[v] - A[v], D[v] - C[v]);
ans[v] = (ans[v] - (D[v] - C[v] - B[v] + A[v])) / 2;
}
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int Q;
cin >> N >> Q;
int i;
for (i = 1; i < N; i++) cin >> L[i] >> R[i];
int op;
for (i = 1; i <= Q; i++) {
cin >> op;
if (op == 1) {
M++;
cin >> P[M] >> S[M] >> E[M];
}
else {
cin >> A[i] >> B[i] >> C[i] >> D[i], qt[i] = M;
if (A[i] == C[i]) ans[i] = max(0ll, B[i] - D[i]);
}
}
if (N == 1) {
for (i = 1; i <= Q; i++) if (A[i]) cout << ans[i] << Ln;
return 0;
}
for (i = 1; i <= Q; i++) if (A[i] && A[i] < C[i]) qv[qt[i]].push_back(i);
solve();
for (i = 1; i <= N / 2; i++) swap(L[i], L[N - i]), swap(R[i], R[N - i]);
for (i = 1; i <= M; i++) P[i] = N - P[i];
for (i = 1; i <= Q; i++) if (A[i]) A[i] = N + 1 - A[i], C[i] = N + 1 - C[i];
for (i = 0; i <= M; i++) qv[i].clear();
for (i = 1; i <= Q; i++) if (A[i] && A[i] < C[i]) qv[qt[i]].push_back(i);
solve();
for (i = 1; i <= Q; i++) if (A[i]) cout << ans[i] << ln;
}
Compilation message
timeleap.cpp: In function 'node operator+(node, node)':
timeleap.cpp:60:1: warning: control reaches end of non-void function [-Wreturn-type]
60 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
54484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
504 ms |
77744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
54484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
