oj.uz

답안 #431743

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
431743 2021-06-17T14:59:20 Z errorgorn 수확 (JOI20_harvest) C++17
0 / 100
 5000 ms 9112 KB 
#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[200005];
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){
		auto iter=lb(all(pos),(arr[x]+k)%l)-pos.begin();
		assert(iter!=sz(pos));
		
		nxt[x]=ii(iter%n,(pos[iter]-(arr[x]+k)%l)+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();
		assert(iter!=sz(pos));
		assert(pos[iter]-brr[x]>0);
		
		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]);
		assert(t[curr].back()+cycl[curr]==ctime);
	}
	
	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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 6732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5039 ms 9112 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 6732 KB Output isn't correct
2 Halted 0 ms 0 KB -