Submission #115263

#	Time	Username	Problem	Language	Result	Execution time	Memory
115263		AngusRitossa	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	100 / 100	2956 ms	108320 KiB

timeleap

#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));
}
int A[300010], B[300010], C[300010], D[300010], T[300010], L[300010], R[300010], l[300010], r[300010];
ll ANS[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()
{
	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:283: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:284: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:287:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &T[i]);
   ~~~~~^~~~~~~~~~~~~
timeleap.cpp:288: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:289: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: 66 / 66