#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef pair<pair<int, int>, pair<int, int> > piiii;
int n, q;
ll l[300010], r[300010];
piiii rangetree[300010*4];
pair<int, int> maxmin(pair<int, int> a, pair<int, int> b)
{
if (a.first == b.first) return min(a, b);
else return max(a, b);
}
void update(int node, pair<int, int> val, int curr = 1, int cstart = 0, int cend = 300000)
{
if (cstart == cend)
{
rangetree[curr] = { { val.first, node }, { val.second, node } };
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].first = maxmin(rangetree[2*curr].first, rangetree[2*curr+1].first);
rangetree[curr].second = min(rangetree[2*curr].second, rangetree[2*curr+1].second);
}
piiii query(int s, int e, int curr = 1, int cstart = 0, int cend = 300000)
{
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
{
auto a = query(s, e, 2*curr, cstart, mid);
auto b = query(s, e, 2*curr+1, mid+1, cend);
return { maxmin(a.first, b.first), min(a.second, b.second) };
}
}
ll rt2[300010*4];
void upd2(int node, ll val, int curr = 1, int cstart = 0, int cend = 300000)
{
if (cstart == cend)
{
rt2[curr] = val;
return;
}
int mid = (cstart+cend)/2;
if (node <= mid) upd2(node, val, 2*curr, cstart, mid);
else upd2(node, val, 2*curr+1, mid+1, cend);
rt2[curr] = rt2[2*curr]+rt2[2*curr+1];
}
ll qu2(int s, int e, int curr = 1, int cstart = 0, int cend = 300000)
{
if (s <= cstart && cend <= e) return rt2[curr];
int mid = (cstart+cend)/2;
if (e <= mid) return qu2(s, e, 2*curr, cstart, mid);
else if (s > mid) return qu2(s, e, 2*curr+1, mid+1, cend);
else return qu2(s, e, 2*curr, cstart, mid)+qu2(s, e, 2*curr+1, mid+1, cend);
}
pair<int, int> firstonleft(int a, int hei)
{
int s = 0;
int e = a-1;
while (s != e)
{
int m = (s+e+1)/2;
auto q = query(m, a-1);
if (q.first.first > hei || q.second.first < hei) s = m;
else e = m-1;
}
int type = l[s] > hei; // if 1 above, if 0 below
return { s, type };
}
bool firstonleftactually0(int a, int hei, bool checkl)
{
int s = 0;
int e = a-1;
while (s != e)
{
int m = (s+e+1)/2;
auto q = query(m, a-1);
if (checkl)
{
if (q.first.first >= hei || q.second.first < hei) s = m;
else e = m-1;
}
else
{
if (q.first.first > hei || q.second.first <= hei) s = m;
else e = m-1;
}
}
if (checkl) return l[s] == hei;
else return r[s] == hei;
}
pair<int, int> firstonright(int a, int hei)
{
int s = a+1;
int e = n+1;
while (s != e)
{
int m = (s+e)/2;
auto q = query(a+1, m);
if (q.first.first > hei || q.second.first < hei) e = m;
else s = m+1;
}
int type = l[s] > hei; // if 1 above, if 0 below
return { s, type };
}
set<pair<int, int> > mnmx;
void checkforlocalstuff(int a)
{
// Check if l is local max
upd2(a, 0);
auto i = firstonleft(a, l[a]);
auto j = firstonright(a, l[a]);
if (!i.second && !j.second && !firstonleftactually0(a, l[a], 1))
{
D("local max %d\n", a);
mnmx.insert({a, 0});
upd2(a, l[a]);
}
else
{
mnmx.erase({a, 0});
}
// Check if r is local min
i = firstonleft(a, r[a]);
j = firstonright(a, r[a]);
if (i.second && j.second && !firstonleftactually0(a, r[a], 0))
{
D("local min %d\n", a);
mnmx.insert({a, 1});
upd2(a, -r[a]);
}
else
{
mnmx.erase({a, 1});
}
}
ll A[300010], B[300010], C[300010], D[300010], T[300010], L[300010], R[300010], ANS[300010];
void dothing(bool reverse)
{
mnmx.clear();
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] });
}
update(0, { 2e9, -2e9 });
update(n, { 2e9, -2e9 });
// Find local max and mins
for (int i = 1; i < n; i++)
{
checkforlocalstuff(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;
update(a, { l[a], r[a] });
// update me
checkforlocalstuff(a);
// check thing before me
auto it = mnmx.lower_bound({a, 0});
if (it != mnmx.begin())
{
--it;
int thing = it->first;
checkforlocalstuff(thing);
}
{
it = mnmx.lower_bound({a, 0});
int thing = 1;
if (it != mnmx.begin()) thing = prev(it)->first+1;
auto q = query(thing, a);
// checkforlocalstuff(q.first.second);
// checkforlocalstuff(q.second.second);
}
it = mnmx.lower_bound({a, 2});
if (it != mnmx.end())
{
int thing = it->first;
checkforlocalstuff(thing);
}
{
it = mnmx.lower_bound({a, 2});
int thing = n-1;
if (it != mnmx.end()) thing = it->first-1;
auto q = query(a, thing);
// checkforlocalstuff(q.first.second);
// checkforlocalstuff(q.second.second);
}
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;
}
ll am = 0;
if (b < l[a]) b = l[a];
if (b > r[a]) am += b-r[a], b = r[a];
D("b %lld d %lld am %lld\n", b, d, am);
// find first occuring secondhalf local thingo
auto it = mnmx.lower_bound({a, -1});
if (it == mnmx.end() || it->first >= c)
{
// There are none in between
auto q = query(a, c-1);
auto mn = q.second; // mn top
auto mx = q.first; // mx bot
ll currloc = b;
ll ans = am;
if (mn.second < mx.second)
{
// go down to mn if its below
if (mn.first < currloc)
{
ans += currloc-mn.first;
currloc = mn.first;
}
// go up to mx if its above
currloc = max(currloc, (ll)mx.first);
// go down to end
ans += max(0ll, currloc-d);
}
else
{
// go up to mx if its above
currloc = max(currloc, (ll)mx.first);
// go down to mn if its below
if (mn.first < currloc)
{
ans += currloc-mn.first;
currloc = mn.first;
}
// go down to end
ans += max(0ll, currloc-d);
}
D("none between: ");
ANS[i] = ans;
}
else
{
auto it2 = prev(mnmx.lower_bound({ c, -1 }));
ll ans = am;
if (it == it2)
{
// one in between
if (it->second) // Local min
{
ll mxbefore = query(a, it->first).first.first;
mxbefore = max(mxbefore, b);
ll mxafter = query(it->first, c-1).first.first;
mxafter = max(mxafter, d);
// move down to the local mn if needed
ll pos = mxbefore;
ll lmnheight = r[it->first];
if (lmnheight < pos) ans += pos-lmnheight, pos = lmnheight;
// move down/up to mx after
ans += max(0ll, pos-mxafter);
pos = mxafter;
// move up/down to end
ans += max(0ll, pos-d);
}
else // Local max
{
ll mnbefore = query(a, it->first).second.first;
mnbefore = min(mnbefore, b);
ll mnafter = query(it->first, c-1).second.first;
mnafter = min(mnafter, d);
// move down to first thing
ll pos = b;
ans += pos-mnbefore;
pos = mnbefore;
// go up to local max if needed
pos = max(pos, l[it->first]);
ans += max(0ll, pos-mnafter);
}
D("one between: ");
ANS[i] = ans;
}
else
{
// two in between
if (it->second) // first is local min
{
ll mxbefore = query(a, it->first).first.first;
mxbefore = max(mxbefore, b);
mxbefore = max(mxbefore, r[it->first]);
ans += mxbefore;
}
else // first is local max
{
ll mnbefore = query(a, it->first).second.first;
mnbefore = min(mnbefore, b);
mnbefore = min(mnbefore, l[it->first]);
ans += b-mnbefore;
}
if (it2->second) // last is local min
{
ll mxbefore = query(it2->first, c-1).first.first;
mxbefore = max(mxbefore, d);
mxbefore = max(mxbefore, r[it2->first]);
ans += mxbefore-d;
}
else // last is local max
{
ll mnbefore = query(it2->first, c-1).second.first;
mnbefore = min(mnbefore, d);
mnbefore = min(mnbefore, l[it2->first]);
ans -= mnbefore;
}
ans += qu2(a, c-1);
D(">1 between: ");
ANS[i] = ans;
}
}
}
}
int main()
{
scanf("%d%d", &n, &q);
for (int i = 1; i < n; i++) scanf("%lld%lld", &L[i], &R[i]);
for (int i = 0; i < q; i++)
{
scanf("%lld", &T[i]);
if (T[i] == 1) scanf("%lld%lld%lld", &A[i], &B[i], &C[i]);
else scanf("%lld%lld%lld%lld", &A[i], &B[i], &C[i], &D[i]);
}
dothing(0);
dothing(1);
for (int i = 0; i < q; i++)
{
if (T[i] == 2) printf("%lld\n", ANS[i]);
}
}
Compilation message
timeleap.cpp: In function 'void dothing(bool)':
timeleap.cpp:190:10: warning: variable 'q' set but not used [-Wunused-but-set-variable]
auto q = query(thing, a);
^
timeleap.cpp:204:10: warning: variable 'q' set but not used [-Wunused-but-set-variable]
auto q = query(a, thing);
^
timeleap.cpp: In function 'int main()':
timeleap.cpp:346:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &q);
~~~~~^~~~~~~~~~~~~~~~
timeleap.cpp:347: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]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:350:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &T[i]);
~~~~~^~~~~~~~~~~~~~~
timeleap.cpp:351:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
if (T[i] == 1) scanf("%lld%lld%lld", &A[i], &B[i], &C[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:352:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
else scanf("%lld%lld%lld%lld", &A[i], &B[i], &C[i], &D[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3030 ms |
45236 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
512 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
