Submission #262681

#	Time	Username	Problem	Language	Result	Execution time	Memory
262681		arnold518	Harvest (JOI20_harvest)	C++14	5 / 100	5048 ms	20072 KiB

harvest

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

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

const int MAXN = 4e5;

struct Query
{
	int v; ll t; int p;
};

int N, M, Q;
ll L, C, A[MAXN+10], B[MAXN+10];
Query D[MAXN+10];
ll cyc[MAXN+10];
int vis[MAXN+10];

pll to[MAXN+10];
vector<pll> adj[MAXN+10];

void dfs(int now, ll dist, vector<ll> &V)
{
	vis[now]=true;
	if(now>N) V.push_back(dist);
	for(auto nxt : adj[now])
	{
		if(vis[nxt.first]) continue;
		dfs(nxt.first, dist+nxt.second, V);
	}
}

int main()
{
	scanf("%d%d%lld%lld", &N, &M, &L, &C);
	for(int i=1; i<=N; i++) scanf("%lld", &A[i]);
	for(int i=1; i<=M; i++) scanf("%lld", &B[i]);
	scanf("%d", &Q);
	for(int i=1; i<=Q; i++) scanf("%d%lld", &D[i].v, &D[i].t), D[i].p=i;

	for(int i=1; i<=N; i++)
	{
		ll t=A[i]-C;
		t=(t%L+L)%L;
		int it=upper_bound(A+1, A+N+1, t)-A-1;
		if(it==0) it=N;
		ll v=((A[i]-A[it])%L+L)%L;
		ll w=(C-v+L-1)/L*L+v;
		to[i]={it, w};
		adj[it].push_back({i, w});
		//printf("%d : %d %lld\n", i, to[i].first, to[i].second);
	}

	for(int i=1; i<=M; i++)
	{
		ll t=B[i];
		int it=upper_bound(A+1, A+N+1, t)-A-1;
		if(it==0) it=N;
		ll v=((B[i]-A[it])%L+L)%L;
		to[i+N]={it, v};
		adj[it].push_back({i+N, v});
		//printf("%d : %d %lld\n", i+N, to[i+N].first, to[i+N].second);
	}

	for(int i=1; i<=N+M; i++)
	{
		if(vis[i]) continue;
		vector<int> V, V2;
		int now;
		for(now=i; vis[now]==0; now=to[now].first)
		{
			vis[now]=2;
			V.push_back(now);
		}
		if(vis[now]==1)
		{
			for(auto it : V) vis[it]=1;
			continue;
		}
		for(auto it : V) vis[it]=1;
		int t=now;
		while(!V.empty())
		{
			int p=V.back();
			V2.push_back(p);
			V.pop_back();
			if(p==t) break;
		}
		ll len=0;
		for(auto it : V2) len+=to[it].second;
		for(auto it : V2) cyc[it]=len;
	}
	//for(int i=1; i<=N+M; i++) printf("%d -> %lld\n", i, cyc[i]);

	for(int i=1; i<=Q; i++)
	{
		vector<ll> V;
		for(int j=1; j<=N+M; j++) vis[j]=0;
		dfs(D[i].v, 0, V);

		ll ans=0;
		for(auto it : V)
		{
			if(it>D[i].t) continue;
			if(cyc[D[i].v])	ans+=1+(D[i].t-it)/cyc[D[i].v];
			else ans++;
		}
		printf("%lld\n", ans);
	}
}

Compilation message (stderr)

harvest.cpp: In function 'int main()':
harvest.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |  scanf("%d%d%lld%lld", &N, &M, &L, &C);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:38:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |  for(int i=1; i<=N; i++) scanf("%lld", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~
harvest.cpp:39:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  for(int i=1; i<=M; i++) scanf("%lld", &B[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~
harvest.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
harvest.cpp:41:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |  for(int i=1; i<=Q; i++) scanf("%d%lld", &D[i].v, &D[i].t), D[i].p=i;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 75