Submission #110572

#	Time	Username	Problem	Language	Result	Execution time	Memory
110572		AngusRitossa	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	0 / 100	3 ms	768 KiB

timeleap

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 1010
#ifdef DEBUG
	#define D(x...) printf(x)
#else
	#define D(x...)
#endif
int n, q;
int l[MAXN], r[MAXN];
int l1[MAXN], r1[MAXN], cost[MAXN][2][20], sta[MAXN];
pair<int, int> jump[MAXN][2][20];
vector<int> startsat[MAXN];
pair<int, int> firstjump[MAXN];
int A[MAXN], T1[MAXN], B[MAXN], T2[MAXN];
void makejump()
{
	int sz = 1;
	sta[0] = n;
	l1[n] = 1e15;
	for (int i = n-1; i >= 1; i--)
	{
		while (sz && l1[sta[sz-1]] <= l1[i]) sz--;
		// from l1
		jump[i][0][0] = { sta[sz-1], 0 };
		cost[i][0][0] = 0;
		// from r1
		int s = 0;
		int e = sz-1;
		while (s != e)
		{
			int m = (s+e+1)/2;
			if (r1[i] >= l1[sta[m]]) e = m-1;
			else s = m;
		}
		jump[i][1][0] = { sta[s], 0 };
		cost[i][1][0] = 0;
		sta[sz++] = i;

		for (auto a : startsat[i])
		{
			int s = 0;
			int e = sz-1;
			while (s != e)
			{
				int m = (s+e+1)/2;
				if (T1[a]-A[a] >= l1[sta[m]]) e = m-1;
				else s = m;
			}
			firstjump[a] = { sta[s], 0 };
		}
	}
	sta[0] = n;
	r1[n] = -1e15;
	for (int i = n-1; i >= 1; i--)
	{
		while (sz && r1[sta[sz-1]] >= r1[i]) sz--;
		// from r1
		if (jump[i][1][0].first > sta[sz-1])
		{
			jump[i][1][0] = { sta[sz-1], 1 };
			cost[i][1][0] = r1[i] - r1[sta[sz-1]];
		}
		// from l1
		int s = 0;
		int e = sz-1;
		while (s != e)
		{
			int m = (s+e+1)/2;
			if (l1[i] <= r1[sta[m]]) e = m-1;
			else s = m;
		}
		if (jump[i][0][0].first > sta[s])
		{
			jump[i][0][0] = { sta[s], 1 };
			cost[i][0][0] = l1[i] - r1[sta[s]];
		}
		sta[sz++] = i;


		for (auto a : startsat[i])
		{
			int s = 0;
			int e = sz-1;
			while (s != e)
			{
				int m = (s+e+1)/2;
				if (T1[a]-A[a] <= r1[sta[m]]) e = m-1;
				else s = m;
			}
			firstjump[a] = min(firstjump[a], { sta[s], 1 } );
		}
	}
	jump[n][0][0].first = jump[n][1][0].first = n;
	for (int k = 1; k < 20; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j < 2; j++)
			{
				jump[i][j][k] = jump[jump[i][j][k-1].first][jump[i][j][k-1].second][k-1];
				cost[i][j][k] = cost[i][j][k-1] + cost[jump[i][j][k-1].first][jump[i][j][k-1].second][k-1];
			}
		}
	}
}
#undef int
int main()
{
	#define int long long
	scanf("%lld%lld", &n, &q);
	for (int i = 1; i < n; i++)
	{
		scanf("%lld%lld", &l[i], &r[i]);
		r[i]--;
	}
	for (int i = 1; i < n; i++)
	{
		l1[i] = l[i]-i;
		r1[i] = r[i]-i;
	}
	for (int i = 0; i < q; i++)
	{
		int t;
		scanf("%lld%lld%lld%lld%lld", &t, &A[i], &T1[i], &B[i], &T2[i]);
		if (A[i] < B[i]) startsat[A[i]].push_back(i);
	}
	makejump();
	for (int f = 0; f < q; f++)
	{
		int a, t1, b, t2;
		a = A[f], t1 = T1[f], b = B[f], t2 = T2[f];
		if (a == b)
		{
			if (t1 <= t2) printf("0\n");
			else printf("%lld\n", t1-t2);
		}
		else if (a < b)
		{
			int ans = 0;
			int i = a;
			int j = 0;
			t2-=b;
			// do the first jump
			if (firstjump[f].first < b)
			{
				i = firstjump[f].first;
				j = firstjump[f].second;
				D("jumping to %lld %lld\n", i, j);
				ans += max(0ll, t1-a-r1[i]);
				D("%lld\n", ans);
			}
			for (int k = 19; k >= 0; k--)
			{
				if (jump[i][j][k].first < b)
				{
					ans += cost[i][j][k];
					tie(i, j) = jump[i][j][k];
				}
			}
			if (i != a)
			{
				if (j) t1 = r1[i];
				else t1 = l1[i];
			}
			else t1-=a;
			ans += max(0ll, t1-t2);
			printf("%lld\n", ans);
		}
		else
		{
			int ans = 0;
			for (int i = a-1; i >= b; i--)
			{
				if (t1 < l[i]) t1 = l[i];
				if (t1 > r[i])
				{
					ans += t1-r[i];
					t1 = r[i];
				}
				t1++;
			}
			ans += max(0ll, t1-t2);
			printf("%lld\n", ans);
		}
	}
}

Compilation message (stderr)

timeleap.cpp: In function 'int main()':
timeleap.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
timeleap.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &l[i], &r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld%lld%lld", &t, &A[i], &T1[i], &B[i], &T2[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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