Submission #112495

#	Time	Username	Problem	Language	Result	Execution time	Memory
112495		AngusRitossa	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	34 / 100	3096 ms	65100 KiB

timeleap

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
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 save[300010*4];
int upto, seen[300010*4];
piiii query(int s, int e, int curr = 1, int cstart = 0, int cend = 300000)
{
	if (s <= cstart && cend <= e) return rangetree[curr];
	if (seen[curr] == upto) return save[curr];
	seen[curr] = upto;
	int mid = (cstart+cend)/2;
	if (e <= mid) return save[curr] = query(s, e, 2*curr, cstart, mid);
	else if (s > mid) return save[curr] = 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 save[curr] = { maxmin(a.first, b.first), min(a.second, b.second) };
	}
}
int firstbefore(int node, int hei, int curr = 1, int cstart = 0, int cend = 300000)
{
	if (cstart == cend) return cstart;
	int mid = (cstart+cend)/2;
	if (node-1 <= mid) return firstbefore(node, hei, 2*curr, cstart, mid);
	auto q = query(mid+1, node-1, 2*curr+1, mid+1, cend);
	if (q.first.first > hei || q.second.first < hei) return firstbefore(node, hei, 2*curr+1, mid+1, cend);
	else return firstbefore(node, hei, 2*curr, cstart, mid);
}
int firstafter(int node, int hei, int curr = 1, int cstart = 0, int cend = 300000)
{
	if (cstart == cend) return cstart;
	int mid = (cstart+cend)/2;
	if (node >= mid) return firstafter(node, hei, 2*curr+1, mid+1, cend);
	auto q = query(node+1, mid, 2*curr, cstart, mid);
	if (q.first.first > hei || q.second.first < hei) return firstafter(node, hei, 2*curr, cstart, mid);
	else return firstafter(node, hei, 2*curr+1, mid+1, cend);
}
int firstbefore0(int node, int hei, bool checkl, int curr = 1, int cstart = 0, int cend = 300000)
{
	if (cstart == cend) return cstart;
	int mid = (cstart+cend)/2;
	if (node-1 <= mid) return firstbefore0(node, hei, checkl, 2*curr, cstart, mid);
	auto q = query(mid+1, node-1, 2*curr+1, mid+1, cend);
	if (checkl) 
	{
		if (q.first.first >= hei || q.second.first < hei) return firstbefore0(node, hei, checkl, 2*curr+1, mid+1, cend);
	}
	else 
	{
		if (q.first.first > hei || q.second.first <= hei) return firstbefore0(node, hei, checkl, 2*curr+1, mid+1, cend);
	}
	return firstbefore0(node, hei, checkl, 2*curr, cstart, mid);
}
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)
{
	upto++;
	int s = firstbefore(a, hei);
	int type = l[s] > hei; // if 1 above, if 0 below
	return { s, type };
}
bool firstonleftactually0(int a, int hei, bool checkl)
{
	upto++;
	int s = firstbefore0(a, hei, checkl);
	if (checkl) return l[s] == hei;
	else return r[s] == hei;
}
pair<int, int> firstonright(int a, int hei)
{
	upto++;
	int s = firstafter(a, hei);
	int type = l[s] > hei; // if 1 above, if 0 below
	return { s, type };
}
set<pair<int, int> > mnmx;
int was[300010];
void checkforlocalstuff(int a)
{
	// Check if l is local max
	if (!firstonleft(a, l[a]).second && !firstonright(a, l[a]).second) 
	{
		if (!firstonleftactually0(a, l[a], 1))
		{
			D("local max %d\n", a);
			if (was[a] != 1) mnmx.insert({a, 0}), upd2(a, l[a]);
			if (was[a] != 1 && was[a]) mnmx.erase({a, 1});
			was[a] = 1;
		}
		else
		{
			if (was[a] == 1 || was[a] == -1) mnmx.erase({a, 0});
			if (was[a] == 2 || was[a] == -1) mnmx.erase({a, 1});
			if (was[a]) upd2(a, 0);
			was[a] = 0;
		}
	}
	else
	{
		if (was[a] == 1 || was[a] == -1) mnmx.erase({a, 0});
		if (firstonleft(a, r[a]).second && firstonright(a, r[a]).second && !firstonleftactually0(a, r[a], 0)) 
		{
			D("local min %d\n", a);
			if (was[a] != 2) mnmx.insert({a, 1}), upd2(a, -r[a]);
			was[a] = 2;
		}
		else
		{
			if (was[a] == 2 || was[a] == -1) mnmx.erase({a, 1});
			if (was[a]) upd2(a, 0);
			was[a] = 0;
		}

	}
}
int A[300010], B[300010], C[300010], D[300010], T[300010], L[300010], R[300010];
ll ANS[300010];
void dothing(bool reverse)
{
	mnmx.clear();
	fill_n(rt2, 300010*4, 0ll);
	fill_n(was, 300010, 0);
	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;
			was[a] = -1;
			l[a] = x-a, r[a] = y-a-1;
			update(a, { l[a], r[a] });
			// update me
			checkforlocalstuff(a);
			// check thing before me
			if (a != 1)
			{
				auto it = mnmx.lower_bound({a, 0});
				int thing = 1;
				if (it != mnmx.begin()) thing = (--it)->first;
				upto++;
				auto q = query(thing, a-1);
				checkforlocalstuff(q.first.second);
				checkforlocalstuff(q.second.second);
			}
			if (a != n-1)
			{
				auto it = mnmx.lower_bound({a, 2});
				int thing = n-1;
				if (it != mnmx.end()) thing = it->first;
				upto++;
				auto q = query(a+1, 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
			upto++;
			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
				{
					upto++;
					ll mxbefore = query(a, it->first).first.first;
					mxbefore = max(mxbefore, b);
					upto++;
					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
				{
					upto++;
					ll mnbefore = query(a, it->first).second.first;
					mnbefore = min(mnbefore, b);
					upto++;
					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
				{
					upto++;
					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
				{
					upto++;
					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
				{
					upto++;
					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
				{
					upto++;
					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("%d%d", &L[i], &R[i]);
	for (int i = 0; i < q; i++)
	{
		scanf("%d", &T[i]);
		if (T[i] == 1) scanf("%d%d%d", &A[i], &B[i], &C[i]);
		else scanf("%d%d%d%d", &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 (stderr)

timeleap.cpp: In function 'int main()':
timeleap.cpp:370: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:371: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("%d%d", &L[i], &R[i]);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:374:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &T[i]);
   ~~~~~^~~~~~~~~~~~~
timeleap.cpp:375:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   if (T[i] == 1) scanf("%d%d%d", &A[i], &B[i], &C[i]);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:376:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   else scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]);
        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 30 / 30
• Subtask 3: 0 / 66