oj.uz

답안 #434023

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
434023 2021-06-20T14:09:37 Z errorgorn 수확 (JOI20_harvest) C++17
0 / 100
 5000 ms 12012 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){
    		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]);
    		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 Correct 5 ms 6860 KB Output is correct
2 Correct 27 ms 7108 KB Output is correct
3 Correct 126 ms 7116 KB Output is correct
4 Execution timed out 5026 ms 6860 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 6860 KB Output is correct
2 Correct 27 ms 7108 KB Output is correct
3 Correct 126 ms 7116 KB Output is correct
4 Execution timed out 5026 ms 6860 KB Time limit exceeded
5 Halted 0 ms 0 KB -