Submission #741714

#	Time	Username	Problem	Language	Result	Execution time	Memory
741714		arnold518	Bitaro's travel (JOI23_travel)	C++17	100 / 100	283 ms	11220 KiB

travel

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

int N, A[MAXN+10], Q;

struct SEG1
{
	int tree[MAXN*4+10];
	void init(int node, int tl, int tr)
	{
		if(tl==tr)
		{
			tree[node]=A[tl]+A[tl]-A[tl+1];
			return;
		}
		int mid=tl+tr>>1;
		init(node*2, tl, mid);
		init(node*2+1, mid+1, tr);
		tree[node]=min(tree[node*2], tree[node*2+1]);
	}
	int query(int node, int tl, int tr, int l, int r, int k)
	{
		if(r<tl || tr<l) return -1;
		if(l<=tl && tr<=r && tree[node]>k) return -1;
		if(tl==tr) return tl;
		int mid=tl+tr>>1, ret;
		ret=query(node*2, tl, mid, l, r, k);
		if(ret!=-1) return ret;
		ret=query(node*2+1, mid+1, tr, l, r, k);
		return ret;
	}
}seg1;

struct SEG2
{
	int tree[MAXN*4+10];
	void init(int node, int tl, int tr)
	{
		if(tl==tr)
		{
			tree[node]=A[tl]+A[tl]-A[tl-1];
			return;
		}
		int mid=tl+tr>>1;
		init(node*2, tl, mid);
		init(node*2+1, mid+1, tr);
		tree[node]=max(tree[node*2], tree[node*2+1]);
	}
	int query(int node, int tl, int tr, int l, int r, int k)
	{
		if(r<tl || tr<l) return -1;
		if(l<=tl && tr<=r && tree[node]<=k) return -1;
		if(tl==tr) return tl;
		int mid=tl+tr>>1, ret;
		ret=query(node*2+1, mid+1, tr, l, r, k);
		if(ret!=-1) return ret;
		ret=query(node*2, tl, mid, l, r, k);
		return ret;
	}
}seg2;

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d", &A[i]);
	A[0]=-1e9+100; A[N+1]=2e9+100;

	seg1.init(1, 1, N);
	seg2.init(1, 1, N);

	scanf("%d", &Q);
	while(Q--)
	{
		int x;
		ll ans=0;
		scanf("%d", &x);
		int t=lower_bound(A+1, A+N+1, x)-A;
		int l, r;
		if(x-A[t-1]<=A[t]-x) l=r=t-1, ans+=x-A[t-1];
		else l=r=t, ans+=A[t]-x;

		int d=0;
		while(!(l==1 && r==N))
		{
			//printf("%d %d : %lld\n", l, r, ans);
			if(l==1 || r==N) { ans+=A[N]-A[1]; break; }
			else if(d==0)
			{
				int t=seg1.query(1, 1, N, r, N, A[l-1]);
				if(t!=-1)
				{
					r=t;
					ans+=A[r]-A[l];
				}
			}
			else
			{
				int t=seg2.query(1, 1, N, 1, l, A[r+1]);
				if(t!=-1)
				{
					l=t;
					ans+=A[r]-A[l];
				}
			}
			d=1-d;
		}
		printf("%lld\n", ans);
	}
}

Compilation message (stderr)

travel.cpp: In member function 'void SEG1::init(int, int, int)':
travel.cpp:22:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |   int mid=tl+tr>>1;
      |           ~~^~~
travel.cpp: In member function 'int SEG1::query(int, int, int, int, int, int)':
travel.cpp:32:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |   int mid=tl+tr>>1, ret;
      |           ~~^~~
travel.cpp: In member function 'void SEG2::init(int, int, int)':
travel.cpp:50:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |   int mid=tl+tr>>1;
      |           ~~^~~
travel.cpp: In member function 'int SEG2::query(int, int, int, int, int, int)':
travel.cpp:60:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |   int mid=tl+tr>>1, ret;
      |           ~~^~~
travel.cpp: In function 'int main()':
travel.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
travel.cpp:71:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |  for(int i=1; i<=N; i++) scanf("%d", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~
travel.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
travel.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 55 / 55