oj.uz

답안 #941883

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
941883 2024-03-09T15:54:00 Z MilosMilutinovic 수확 (JOI20_harvest) C++14
5 / 100
 5000 ms 24312 KB 
#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,m,l,c,q,T;
int a[200005],b[200005],prv[200005],deg[200005],rt[200005],fenw[200005],dfn[200005],dfo[200005];
ll d[200005];
vector<pair<ll,int>> qs[200005];
vector<array<ll,4>> ev;
vector<ll> my[200005];
ll ans[200005];
vector<int> topo,ch[200005];
bool oncyc[200005];

ll calc(ll x){return x>=c?x:((c-x+l-1)/l)*1ll*l+x;}

int getprv(int x){
	int d=c%l;
	if(a[1]<=x-d){
		int l=1,r=n,p=1;
		while(l<=r){
			int mid=(l+r)/2;
			if(a[mid]<=x-d) l=mid+1,p=mid; 
			else r=mid-1;
		}
		return p;
	}else{
		int l=1,r=n,p=1;
		while(l<=r){
			int mid=(l+r)/2;
			if(x+::l-a[mid]>=d) l=mid+1,p=mid; 
			else r=mid-1;
		}
		return p;
	}
}

void change(int p,int v){
	for(;p<200005;p|=p+1) fenw[p]+=v;  
}

int ask(int p){
	int v=0;
	for(;p>=0;p=(p&(p+1))-1) v+=fenw[p];
	return v;
}

void dfs1(int x,ll d){
	dfn[x]=++T;
	for(auto&p:my[x]) ev.pb({d+p,0,dfn[x],0});
	for(auto&p:qs[x]) ev.pb({p.fi+d,1,x,p.se});
	for(auto&p:my[x]) my[rt[x]].pb(p+d);
	for(int v:ch[x]){
		rt[v]=rt[x];
		ll w=calc(a[x]<=a[v]?a[v]-a[x]:a[v]+l-a[x]);
		dfs1(v,d+w);
	}
	dfo[x]=T;
}

int main(){
	n=readint(); m=readint(); l=readint(); c=readint();
	for(int i=1;i<=n;i++) a[i]=readint();
	for(int i=1;i<=m;i++) b[i]=readint();
	q=readint();
	for(int i=1;i<=q;i++){
		int v=readint();
		ll t=readint();
		qs[v].pb(mp(t,i));
	}
	for(int i=1;i<=n;i++) prv[i]=getprv(a[i]);
	for(int i=1;i<=m;i++){
		int idx;
		if(a[1]<=b[i]){
			int l=1,r=n;
			while(l<=r){
				int mid=(l+r)/2;
				if(a[mid]<=b[i]) idx=mid,l=mid+1;
				else r=mid-1;
			}
		}else idx=n;
		my[idx].pb((b[i]-a[idx]+l)%l);
	}
	for(int i=1;i<=n;i++) deg[prv[i]]++;
	for(int i=1;i<=n;i++) if(deg[i]==0) topo.pb(i);
	for(int i=0;i<(int)topo.size();i++){
		int v=topo[i];
		deg[prv[v]]--;
		if(deg[prv[v]]==0) topo.pb(prv[v]);
	}
	for(int i=1;i<=n;i++) oncyc[i]=true;
	for(int i:topo) oncyc[i]=false;
	for(int i=1;i<=n;i++) ch[prv[i]].pb(i);
	for(int i=1;i<=n;i++){
		if(oncyc[i]||!oncyc[prv[i]]) continue;
		rt[i]=prv[i];
		ll w=calc(a[prv[i]]<=a[i]?a[i]-a[prv[i]]:a[i]+l-a[prv[i]]);
		T=0;
		ev.clear();
		dfs1(i,w);
		sort(ev.begin(),ev.end());
		for(auto&p:ev){
			if(p[1]==0){
				change(p[2],1);
			}else{
				ans[p[3]]=ask(dfo[p[2]])-ask(dfn[p[2]]-1);
			}
		}
		for(auto&p:ev) if(p[1]==0) change(p[2],-1);
	}
	for(int i=1;i<=n;i++){
		if(!oncyc[i]) continue;
		vector<int> f;
		int ver=i;
		while(oncyc[ver]){
			f.pb(ver);
			oncyc[ver]=false;
			ver=prv[ver];
		}
		int sz=(int)f.size();
		vector<int> tmp=f;
		for(int i=0;i<sz;i++){
			f.clear();
			int ver=tmp[i];
			for(int j=0;j<sz;j++) f.pb(ver),ver=prv[ver];
			d[0]=0;
			for(int j=1;j<sz;j++){
				ll w=calc(a[f[j]]<=a[f[j-1]]?a[f[j-1]]-a[f[j]]:a[f[j-1]]+l-a[f[j]]);
				d[j]=d[j-1]+w;
			}
			ll len=d[sz-1]+calc(a[f[0]]<=a[f.back()]?a[f.back()]-a[f[0]]:a[f.back()]+l-a[f[0]]);
			if(f.size()==1) len=calc(l);
			for(int j=0;j<sz;j++){
				for(auto&p:my[f[0]]){
					for(auto&pp:qs[f[j]]){
						ans[pp.se]+=max(0ll,pp.fi-d[j]-p+len)/len;
					}
				}
			}
		}
	}
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 21080 KB Output is correct
2 Correct 6 ms 21080 KB Output is correct
3 Correct 85 ms 21140 KB Output is correct
4 Correct 8 ms 23644 KB Output is correct
5 Correct 7 ms 24188 KB Output is correct
6 Correct 8 ms 24092 KB Output is correct
7 Correct 7 ms 24312 KB Output is correct
8 Correct 6 ms 23128 KB Output is correct
9 Correct 7 ms 23224 KB Output is correct
10 Correct 7 ms 23644 KB Output is correct
11 Correct 6 ms 23624 KB Output is correct
12 Correct 108 ms 21312 KB Output is correct
13 Correct 117 ms 21348 KB Output is correct
14 Correct 65 ms 21340 KB Output is correct
15 Correct 8 ms 23948 KB Output is correct
16 Correct 7 ms 24092 KB Output is correct
17 Correct 7 ms 23888 KB Output is correct
18 Correct 8 ms 23900 KB Output is correct
19 Correct 7 ms 24152 KB Output is correct
20 Correct 6 ms 23900 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 21080 KB Output is correct
2 Correct 6 ms 21080 KB Output is correct
3 Correct 85 ms 21140 KB Output is correct
4 Correct 8 ms 23644 KB Output is correct
5 Correct 7 ms 24188 KB Output is correct
6 Correct 8 ms 24092 KB Output is correct
7 Correct 7 ms 24312 KB Output is correct
8 Correct 6 ms 23128 KB Output is correct
9 Correct 7 ms 23224 KB Output is correct
10 Correct 7 ms 23644 KB Output is correct
11 Correct 6 ms 23624 KB Output is correct
12 Correct 108 ms 21312 KB Output is correct
13 Correct 117 ms 21348 KB Output is correct
14 Correct 65 ms 21340 KB Output is correct
15 Correct 8 ms 23948 KB Output is correct
16 Correct 7 ms 24092 KB Output is correct
17 Correct 7 ms 23888 KB Output is correct
18 Correct 8 ms 23900 KB Output is correct
19 Correct 7 ms 24152 KB Output is correct
20 Correct 6 ms 23900 KB Output is correct
21 Execution timed out 5041 ms 24136 KB Time limit exceeded
22 Halted 0 ms 0 KB -