제출 #434025

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434025		errorgorn	수확 (JOI20_harvest)	C++17	0 / 100	5091 ms	8880 KiB

harvest

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'
 
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
 
#define rep(x,s,e) for (ll x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll) (x).size()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
ll n,m,l,k,q;
ll arr[200005];
ll brr[200005];
 
vector<ll> pos;
 
ii nxt[200005];
 
bool vis[3005];
bool onstk[200005];
ll cycl[200005];
 
void dfs(int i){
	vis[i]=true;
	onstk[i]=true;
	
	if (!vis[nxt[i].fi]) dfs(nxt[i].fi);
	else if (vis[nxt[i].fi]){
		ll curr=i;
		ll len=0;
		do{
			len+=nxt[curr].se;
			curr=nxt[curr].fi;
		} while (curr!=i);
		
		do{
			cycl[curr]=len;
			curr=nxt[curr].fi;
		} while (curr!=i);
	}
	
	onstk[i]=false;
}
 
vector<ll> t[200005];
 
int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>m>>l>>k;
	rep(x,0,n) cin>>arr[x];
	rep(x,0,m) cin>>brr[x];
	
	rep(x,0,n) arr[x]=l-arr[x];
	rep(x,0,m) brr[x]=l-brr[x];
	reverse(arr,arr+n);
	reverse(brr,brr+m);
	
	rep(z,0,2) rep(x,0,n) pos.pub(arr[x]+z*l);
	
	rep(x,0,n){
		int temp=(arr[x]+k)%l;
		if (temp==0) temp=l;
		auto iter=lb(all(pos),temp)-pos.begin();
		
		nxt[x]=ii(iter%n,(pos[iter]-temp)+k);
	}
	
	
	rep(x,0,n){
		//cout<<x<<" "<<arr[x]<<" "<<nxt[x].fi<<" "<<nxt[x].se<<endl;
	}
	
	memset(cycl,-1,sizeof(cycl));
	rep(x,0,n) if (!vis[x]){
		dfs(x);
	}
	
	//rep(x,0,n) cout<<cycl[x]<<" "; cout<<endl;
	
	rep(x,0,m){
		auto iter=lb(all(pos),brr[x])-pos.begin();
		
		ll curr=iter%n;
		ll ctime=pos[iter]-brr[x];
		
		//cout<<"debug: "<<brr[x]<<" "<<curr<<" "<<ctime<<endl;
		
		memset(vis,false,sizeof(vis));
		do{
			vis[curr]=true;
			t[curr].pub(ctime);
			//cout<<curr<<" "<<ctime<<endl;
			
			ctime+=nxt[curr].se;
			curr=nxt[curr].fi;
		} while (!vis[curr]);
	}
	
	cin>>q;
	ll a,b;
	while (q--){
		cin>>a>>b;
		a=n-a;
		
		assert(0<=a && a<n);
		
		ll ans=0;
		if (cycl[a]==-1){
			for (auto &it:t[a]) if (it<=b) ans++;
		}
		else{
			for (auto &it:t[a]) if (it<=b) ans+=(b-it)/cycl[a]+1;
		}
		
		cout<<ans<<endl;
	}
}

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