제출 #110584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
110584		AngusRitossa	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	30 / 100	2678 ms	343336 KiB

timeleap

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 300010
#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], swapped[300010];
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;
	sz = 1;
	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];
			}
		}
	}
}
int anss[300010];
#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) anss[f] = 0;
			else anss[f] = t1-t2;
		}
		else if (a < b)
		{
			int ans = 0;
			int i = a;
			int jumped = 0;
			int j = 0;
			t2-=b;
			// do the first jump
			if (firstjump[f].first < b)
			{
				jumped = 1;
				i = firstjump[f].first;
				j = firstjump[f].second;
				D("jumping to %lld %lld t1 r1 %lld %lld from %lld\n", i, j, t1, r1[i], a);
				ans += max(0ll, t1-a-r1[i]);
				D("%lld\n", ans);
			}
			if (jumped)
			{
				for (int k = 19; k >= 0; k--)
				{
					if (jump[i][j][k].first < b)
					{
						D("jumping again to %lld %lld cost %lld k %lld\n", jump[i][j][k].first, jump[i][j][k].second, cost[i][j][k], k);
						ans += cost[i][j][k];
						tie(i, j) = jump[i][j][k];
					}
				}
			}	
			if (jumped)
			{
				if (j) t1 = r1[i];
				else t1 = l1[i];
			}
			else t1-=a;
			ans += max(0ll, t1-t2);
			anss[f] = ans;
		}
	}
	for (int i = 1; i < n; i++)
	{
		l1[i] = l[n-i]-i;
		r1[i] = r[n-i]-i;
		startsat[i].clear();
	}
	for (int i = 0; i < q; i++)
	{
		if (A[i] > B[i]) 
		{
			swapped[i] = 1;
			A[i] = n-A[i]+1;
			B[i] = n-B[i]+1;
			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 (swapped[f])
		{
			int ans = 0;
			int i = a;
			int jumped = 0;
			int j = 0;
			t2-=b;
			// do the first jump
			if (firstjump[f].first < b)
			{
				jumped = 1;
				i = firstjump[f].first;
				j = firstjump[f].second;
				D("jumping to %lld %lld t1 r1 %lld %lld from %lld\n", i, j, t1, r1[i], a);
				ans += max(0ll, t1-a-r1[i]);
				D("%lld\n", ans);
			}
			if (jumped)
			{
				for (int k = 19; k >= 0; k--)
				{
					if (jump[i][j][k].first < b)
					{
						D("jumping again to %lld %lld cost %lld k %lld\n", jump[i][j][k].first, jump[i][j][k].second, cost[i][j][k], k);
						ans += cost[i][j][k];
						tie(i, j) = jump[i][j][k];
					}
				}
			}	
			if (jumped)
			{
				if (j) t1 = r1[i];
				else t1 = l1[i];
			}
			else t1-=a;
			ans += max(0ll, t1-t2);
			anss[f] = ans;
		}
	}
	for (int i = 0; i < q; i++)
	{
		printf("%lld\n", anss[i]);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

timeleap.cpp: In function 'int main()':
timeleap.cpp:111: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:114: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:125: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: 30 / 30
• Subtask 3: 0 / 66