oj.uz

Submission #434027

# Submission time Handle Problem Language Result Execution time Memory
434027 2021-06-20T14:13:38 Z errorgorn Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 96676 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[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 (onstk[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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6604 KB Output is correct
2 Correct 8 ms 6732 KB Output is correct
3 Correct 103 ms 6964 KB Output is correct
4 Correct 14 ms 10828 KB Output is correct
5 Correct 92 ms 52140 KB Output is correct
6 Correct 95 ms 52176 KB Output is correct
7 Correct 99 ms 52640 KB Output is correct
8 Correct 7 ms 6860 KB Output is correct
9 Correct 7 ms 6860 KB Output is correct
10 Correct 7 ms 6988 KB Output is correct
11 Correct 7 ms 6972 KB Output is correct
12 Correct 191 ms 96676 KB Output is correct
13 Correct 258 ms 96672 KB Output is correct
14 Correct 129 ms 54904 KB Output is correct
15 Correct 50 ms 31960 KB Output is correct
16 Correct 52 ms 32160 KB Output is correct
17 Correct 50 ms 32580 KB Output is correct
18 Correct 43 ms 29536 KB Output is correct
19 Correct 45 ms 30404 KB Output is correct
20 Correct 43 ms 29892 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5070 ms 8876 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6604 KB Output is correct
2 Correct 8 ms 6732 KB Output is correct
3 Correct 103 ms 6964 KB Output is correct
4 Correct 14 ms 10828 KB Output is correct
5 Correct 92 ms 52140 KB Output is correct
6 Correct 95 ms 52176 KB Output is correct
7 Correct 99 ms 52640 KB Output is correct
8 Correct 7 ms 6860 KB Output is correct
9 Correct 7 ms 6860 KB Output is correct
10 Correct 7 ms 6988 KB Output is correct
11 Correct 7 ms 6972 KB Output is correct
12 Correct 191 ms 96676 KB Output is correct
13 Correct 258 ms 96672 KB Output is correct
14 Correct 129 ms 54904 KB Output is correct
15 Correct 50 ms 31960 KB Output is correct
16 Correct 52 ms 32160 KB Output is correct
17 Correct 50 ms 32580 KB Output is correct
18 Correct 43 ms 29536 KB Output is correct
19 Correct 45 ms 30404 KB Output is correct
20 Correct 43 ms 29892 KB Output is correct
21 Execution timed out 5070 ms 8876 KB Time limit exceeded
22 Halted 0 ms 0 KB -