#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
struct zigzag
{
bool isline;
int height; // if line
ll addtoall;
int a, b; // if not line
vector<pair<pair<int, int>, pair<bool, int> > > add; // first pair range of elements, 2nd bool as to whether to add current loc, then add amount
};
zigzag merge(zigzag a, zigzag &b)
{
if (a.isline)
{
for (auto f : b.add)
{
if (f.first.first <= a.height && a.height <= f.first.second)
{
a.addtoall += f.second.second;
if (f.second.first) a.addtoall += a.height;
}
}
if (b.isline)
{
a.addtoall += b.addtoall;
a.height = b.height;
}
else
{
if (b.a > a.height) a.height = b.a;
else if (b.b < a.height) a.height = b.b;
}
return a;
}
else
{
if (b.isline)
{
a.isline = 1;
for (auto f : b.add)
{
if (f.first.first <= a.a && a.a <= f.first.second)
{
ll am = f.second.second;
if (f.second.first) am += a.a;
a.add.push_back({ { -1.1e9, a.a }, { 0, am }});
}
int bot = max(f.first.first, a.a+1);
int top = min(f.first.second, a.b-1);
if (bot <= top)
{
a.add.push_back({ { bot, top }, f.second });
}
if (f.first.first <= a.b && a.b <= f.first.second)
{
ll am = f.second.second;
if (f.second.first) am += a.b;
a.add.push_back({ { a.b, 1.1e9 }, { 0, am }});
}
}
a.addtoall += b.addtoall;
a.height = b.height;
return a;
}
else if (b.a >= a.b) // second one is completely above
{
// just make a into a line and return
a.isline = 1;
a.height = b.a;
return a;
}
else if (b.b <= a.a) // second one is completely below
{
// make into a line, moving all groups down
a.isline = 1;
a.height = b.b;
a.add.clear();
a.add.push_back({ { a.a+1, 1.1e9 }, { 1, -a.height }});
a.add.push_back({ { -1.1e9, a.a }, { 0, a.a-a.height }});
return a;
}
else // overlap
{
a.add.clear();
a.b = min(a.b, b.b);
a.a = max(a.a, b.a);
assert(a.a <= a.b);
a.add.push_back({ { a.b, 1.1e9 }, { 1, -a.b } });
if (a.a == a.b)
{
a.isline = 1;
a.height = a.a;
}
return a;
}
}
}
zigzag merge2(zigzag a, zigzag b)
{
if (a.isline)
{
for (auto f : b.add)
{
if (f.first.first <= a.height && a.height <= f.first.second)
{
a.addtoall += f.second.second;
if (f.second.first) a.addtoall += a.height;
}
}
if (b.isline)
{
a.addtoall += b.addtoall;
a.height = b.height;
}
else
{
if (b.a > a.height) a.height = b.a;
else if (b.b < a.height) a.height = b.b;
}
return a;
}
else
{
if (b.isline)
{
a.isline = 1;
for (auto f : b.add)
{
if (f.first.first <= a.a && a.a <= f.first.second)
{
ll am = f.second.second;
if (f.second.first) am += a.a;
a.add.push_back({ { -1.1e9, a.a }, { 0, am }});
}
int bot = max(f.first.first, a.a+1);
int top = min(f.first.second, a.b-1);
if (bot <= top)
{
a.add.push_back({ { bot, top }, f.second });
}
if (f.first.first <= a.b && a.b <= f.first.second)
{
ll am = f.second.second;
if (f.second.first) am += a.b;
a.add.push_back({ { a.b, 1.1e9 }, { 0, am }});
}
}
a.addtoall += b.addtoall;
a.height = b.height;
return a;
}
else if (b.a >= a.b) // second one is completely above
{
// just make a into a line and return
a.isline = 1;
a.height = b.a;
return a;
}
else if (b.b <= a.a) // second one is completely below
{
// make into a line, moving all groups down
a.isline = 1;
a.height = b.b;
a.add.clear();
a.add.push_back({ { a.a+1, 1.1e9 }, { 1, -a.height }});
a.add.push_back({ { -1.1e9, a.a }, { 0, a.a-a.height }});
return a;
}
else // overlap
{
a.add.clear();
a.b = min(a.b, b.b);
a.a = max(a.a, b.a);
assert(a.a <= a.b);
a.add.push_back({ { a.b, 1.1e9 }, { 1, -a.b } });
if (a.a == a.b)
{
a.isline = 1;
a.height = a.a;
}
return a;
}
}
}
zigzag rangetree[300010*4];
void update(int node, pair<int, int> val, int curr = 1, int cstart = 0, int cend = 300010)
{
if (cstart == cend)
{
rangetree[curr].a = val.first, rangetree[curr].b = val.second;
rangetree[curr].add = { { { val.second, 1.1e9 }, { 1, -val.second } } };
if (rangetree[curr].a == rangetree[curr].b)
{
rangetree[curr].isline = 1;
rangetree[curr].height = rangetree[curr].a;
}
else rangetree[curr].isline = 0;
return;
}
int mid = (cstart+cend)/2;
if (node <= mid) update(node, val, 2*curr, cstart, mid);
else update(node, val, 2*curr+1, mid+1, cend);
rangetree[curr] = merge(rangetree[2*curr], rangetree[2*curr+1]);
};
zigzag query(int s, int e, int curr = 1, int cstart = 0, int cend = 300010)
{
if (s <= cstart && cend <= e) return rangetree[curr];
int mid = (cstart+cend)/2;
if (e <= mid) return query(s, e, 2*curr, cstart, mid);
else if (s > mid) return query(s, e, 2*curr+1, mid+1, cend);
else return merge2(query(s, e, 2*curr, cstart, mid), query(s, e, 2*curr+1, mid+1, cend));
}
ll A[300010], B[300010], C[300010], D[300010], T[300010], L[300010], R[300010], ANS[300010], l[300010], r[300010];
int n, q;
void dothing(bool reverse)
{
for (int i = 1; i < n; i++)
{
l[i] = L[i], r[i] = R[i];
if (reverse) l[i] = L[n-i], r[i] = R[n-i];
l[i]-=i;
r[i]-=i+1;
D("%lld %lld\n", l[i], r[i]);
update(i, { l[i], r[i] });
assert(l[i] <= r[i]);
}
for (int i = 0; i < q; i++)
{
ll t, a, b, c, d;
t = T[i];
if (t == 1)
{
ll a = A[i], x = B[i], y = C[i];
if (reverse) a = n-a;
l[a] = x-a, r[a] = y-a-1;
assert(l[a] <= r[a]);
update(a, { l[a], r[a] });
continue;
}
a = A[i], b = B[i], c = C[i], d = D[i];
if (a > c && !reverse) continue;
if (reverse)
{
if (a <= c) continue;
a = n-a+1, c = n-c+1;
}
b-=a, d-=c;
if (a == c)
{
ANS[i] = max(0ll, b-d);
continue;
}
zigzag q = query(a, c-1);
ll ans = q.addtoall;
for (auto f : q.add)
{
if (f.first.first <= b && b <= f.first.second)
{
ans += f.second.second;
if (f.second.first) ans += b;
}
}
int endpoint = q.height;
if (!q.isline)
{
if (b < q.a) endpoint = q.a;
else if (b > q.b) endpoint = q.b;
else endpoint = b;
}
ans += max(0ll, endpoint-d);
ANS[i] = ans;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
for (int i = 1; i < n; i++) scanf("%lld%lld", &L[i], &R[i]);
for (int i = 0; i < q; i++)
{
cin >> T[i];
if (T[i] == 1) cin >> A[i] >> B[i] >> C[i];
else cin >> A[i] >> B[i] >> C[i] >> D[i];
}
dothing(0);
dothing(1);
for (int i = 0; i < q; i++)
{
if (T[i] == 2) cout << ANS[i] << "\n";
}
}
Compilation message
timeleap.cpp: In function 'int main()':
timeleap.cpp:285:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 1; i < n; i++) scanf("%lld%lld", &L[i], &R[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
108 ms |
113400 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 |
345 ms |
147160 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 |
108 ms |
113400 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
