Submission #112396

# Submission time Handle Problem Language Result Execution time Memory
112396 2019-05-19T13:01:37 Z AngusRitossa Bitaro, who Leaps through Time (JOI19_timeleap) C++14
0 / 100
3000 ms 45236 KB
#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 -