oj.uz

Submission #292161

# Submission time Handle Problem Language Result Execution time Memory
292161 2020-09-06T13:06:08 Z TadijaSebez Harvest (JOI20_harvest) C++11
5 / 100
 5000 ms 106872 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pli pair<ll,int>
#define pb push_back
const int N=400050;
int a[N],b[N],go[N],len[N*2],was[N],csz,on_chn[N*2],n,m,l,c,h,lid[N*2],rid[N*2],tid;
ll dep[N*2],chn_len[N],my_chn_len[N],ans[N];
vector<int> E[N*2];
void DFS(int u,ll cl){
	dep[u]+=len[u];
	lid[u]=tid+1;
	if(u>n&&u<=h||u>h+n&&u<=2*h)tid++,my_chn_len[tid]=cl;
	for(int v:E[u])if(!on_chn[v])dep[v]=dep[u],DFS(v,cl);
	rid[u]=tid;
}
const int M=2*N;
int ls[M],rs[M],tsz,root,sz[M];
multiset<ll> ost[M];
ll sub[M];
void Set(int&c,int ss,int se,int qi,ll x,ll y){
	if(!c)c=++tsz;
	sz[c]++;
	sub[c]+=x;
	ost[c].insert(y);
	if(ss==se)return;
	int mid=ss+se>>1;
	if(qi<=mid)Set(ls[c],ss,mid,qi,x,y);
	else Set(rs[c],mid+1,se,qi,x,y);
}
int GetCnt(int c,int ss,int se,int qs,int qe){
	if(qs>qe||qs>se||ss>qe)return 0;
	if(qs<=ss&&qe>=se)return sz[c];
	int mid=ss+se>>1;
	return GetCnt(ls[c],ss,mid,qs,qe)+GetCnt(rs[c],mid+1,se,qs,qe);
}
ll Get(int c,int ss,int se,int qs,int qe){
	if(qs>qe||qs>se||ss>qe)return 0;
	if(qs<=ss&&qe>=se)return sub[c];
	int mid=ss+se>>1;
	return Get(ls[c],ss,mid,qs,qe)+Get(rs[c],mid+1,se,qs,qe);
}
int Lo(int c,int ss,int se,int qs,int qe,ll y){
	if(qs>qe||qs>se||ss>qe)return 0;
	if(qs<=ss&&qe>=se){
		int ans=0;
		for(auto it:ost[c]){
			if(it>y)break;
			ans++;
		}
		return ans;
	}
	int mid=ss+se>>1;
	return Lo(ls[c],ss,mid,qs,qe,y)+Lo(rs[c],mid+1,se,qs,qe,y);
}
void Add(pli p){
	Set(root,1,tid,p.second,p.first/my_chn_len[p.second],p.first%my_chn_len[p.second]);
}
int Count(int l,int r){return GetCnt(root,1,tid,l,r);}
ll Get(int l,int r){return Get(root,1,tid,l,r);}
int Lo(int l,int r,ll y){return Lo(root,1,tid,l,r,y);}
int q,V[N],ord[N];
ll T[N];
int main(){
	scanf("%i %i %i %i",&n,&m,&l,&c);
	for(int i=1;i<=n;i++)scanf("%i",&a[i]),a[i]=l-a[i];
	reverse(a+1,a+1+n);
	for(int i=1;i<=n;i++)a[i+n]=a[i]+l;
	for(int i=1;i<=n;i++){
		int j=lower_bound(a+i,a+i+1+n,a[i]+c%l)-a;
		len[i]=c/l*l+a[j]-a[i];
		if(j>n)j-=n;
		go[i]=j;
	}
	for(int i=1;i<=m;i++){
		scanf("%i",&b[i]);
		b[i]=l-b[i];
		int j=lower_bound(a+1,a+1+2*n,b[i])-a;
		len[n+i]=a[j]-b[i];
		go[n+i]=j>n?j-n:j;
	}
	h=n+m;
	for(int i=1;i<=h;i++){
		E[go[i]].pb(i);
		E[go[i]+h].pb(i+h);
		len[i+h]=len[i];
	}
	for(int i=1;i<=n;i++)if(!was[i]){
		int j=i;csz++;
		while(!was[j])was[j]=csz,j=go[j];
		if(was[j]!=csz)continue;
		int k=j;
		vector<int> chn;
		do{
			chn.pb(k);
			on_chn[k]=on_chn[k+h]=1;
			chn_len[csz]+=len[k];
			k=go[k];
		}while(k!=j);
		reverse(chn.begin(),chn.end());
		ll sum=0;
		for(int k:chn){
			dep[k]=sum;
			DFS(k,chn_len[csz]);
			sum+=len[k];
		}
		for(int k:chn){
			dep[k+h]=sum;
			DFS(k+h,chn_len[csz]);
			sum+=len[k];
		}
	}
	vector<pli> leaf;
	for(int i=n+1;i<=h;i++){
		leaf.pb({dep[i],lid[i]});
		leaf.pb({dep[i+h],lid[i+h]});
	}
	sort(leaf.begin(),leaf.end());
	scanf("%i",&q);
	for(int i=1;i<=q;i++){
		scanf("%i %lld",&V[i],&T[i]);
		V[i]=n-V[i]+1;
		T[i]+=dep[V[i]];
		ord[i]=i;
	}
	sort(ord+1,ord+1+q,[&](int i,int j){return T[i]<T[j];});
	for(int z=1,j=0;z<=q;z++){
		int i=ord[z];
		while(j<leaf.size()&&leaf[j].first<=T[i])Add(leaf[j]),j++;
		if(on_chn[V[i]]){
			int L=lid[V[i]],R=lid[V[i]+h]-1;
			int cnt=Count(L,R);
			ll now=cnt*(T[i]/chn_len[was[V[i]]])-Get(L,R);
			now+=Lo(L,R,T[i]%chn_len[was[V[i]]]);
			ans[i]=now;
		}else{
			ans[i]=Count(lid[V[i]],rid[V[i]]);
		}
	}
	for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
	return 0;
}

Compilation message

harvest.cpp: In function 'void DFS(int, long long int)':
harvest.cpp:13:8: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   13 |  if(u>n&&u<=h||u>h+n&&u<=2*h)tid++,my_chn_len[tid]=cl;
      |     ~~~^~~~~~
harvest.cpp: In function 'void Set(int&, int, int, int, long long int, long long int)':
harvest.cpp:27:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |  int mid=ss+se>>1;
      |          ~~^~~
harvest.cpp: In function 'int GetCnt(int, int, int, int, int)':
harvest.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |  int mid=ss+se>>1;
      |          ~~^~~
harvest.cpp: In function 'long long int Get(int, int, int, int, int)':
harvest.cpp:40:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |  int mid=ss+se>>1;
      |          ~~^~~
harvest.cpp: In function 'int Lo(int, int, int, int, int, long long int)':
harvest.cpp:53:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |  int mid=ss+se>>1;
      |          ~~^~~
harvest.cpp: In function 'int main()':
harvest.cpp:129:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |   while(j<leaf.size()&&leaf[j].first<=T[i])Add(leaf[j]),j++;
      |         ~^~~~~~~~~~~~
harvest.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |  scanf("%i %i %i %i",&n,&m,&l,&c);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:66:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |  for(int i=1;i<=n;i++)scanf("%i",&a[i]),a[i]=l-a[i];
      |                       ~~~~~^~~~~~~~~~~~
harvest.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |   scanf("%i",&b[i]);
      |   ~~~~~^~~~~~~~~~~~
harvest.cpp:119:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  119 |  scanf("%i",&q);
      |  ~~~~~^~~~~~~~~
harvest.cpp:121:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  121 |   scanf("%i %lld",&V[i],&T[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 56960 KB Output is correct
2 Correct 60 ms 61688 KB Output is correct
3 Correct 156 ms 61816 KB Output is correct
4 Correct 59 ms 61176 KB Output is correct
5 Correct 58 ms 61816 KB Output is correct
6 Correct 59 ms 61816 KB Output is correct
7 Correct 57 ms 61808 KB Output is correct
8 Correct 56 ms 61564 KB Output is correct
9 Correct 53 ms 59512 KB Output is correct
10 Correct 56 ms 61560 KB Output is correct
11 Correct 50 ms 59512 KB Output is correct
12 Correct 51 ms 59640 KB Output is correct
13 Correct 123 ms 61688 KB Output is correct
14 Correct 99 ms 61652 KB Output is correct
15 Correct 57 ms 61688 KB Output is correct
16 Correct 57 ms 61688 KB Output is correct
17 Correct 57 ms 61688 KB Output is correct
18 Correct 58 ms 61592 KB Output is correct
19 Correct 56 ms 61592 KB Output is correct
20 Correct 56 ms 61672 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3270 ms 69528 KB Output is correct
2 Correct 426 ms 87416 KB Output is correct
3 Correct 332 ms 99832 KB Output is correct
4 Correct 3330 ms 102392 KB Output is correct
5 Correct 331 ms 106620 KB Output is correct
6 Correct 297 ms 106872 KB Output is correct
7 Correct 263 ms 85984 KB Output is correct
8 Correct 264 ms 85988 KB Output is correct
9 Correct 4962 ms 100688 KB Output is correct
10 Execution timed out 5048 ms 97948 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 56960 KB Output is correct
2 Correct 60 ms 61688 KB Output is correct
3 Correct 156 ms 61816 KB Output is correct
4 Correct 59 ms 61176 KB Output is correct
5 Correct 58 ms 61816 KB Output is correct
6 Correct 59 ms 61816 KB Output is correct
7 Correct 57 ms 61808 KB Output is correct
8 Correct 56 ms 61564 KB Output is correct
9 Correct 53 ms 59512 KB Output is correct
10 Correct 56 ms 61560 KB Output is correct
11 Correct 50 ms 59512 KB Output is correct
12 Correct 51 ms 59640 KB Output is correct
13 Correct 123 ms 61688 KB Output is correct
14 Correct 99 ms 61652 KB Output is correct
15 Correct 57 ms 61688 KB Output is correct
16 Correct 57 ms 61688 KB Output is correct
17 Correct 57 ms 61688 KB Output is correct
18 Correct 58 ms 61592 KB Output is correct
19 Correct 56 ms 61592 KB Output is correct
20 Correct 56 ms 61672 KB Output is correct
21 Correct 3270 ms 69528 KB Output is correct
22 Correct 426 ms 87416 KB Output is correct
23 Correct 332 ms 99832 KB Output is correct
24 Correct 3330 ms 102392 KB Output is correct
25 Correct 331 ms 106620 KB Output is correct
26 Correct 297 ms 106872 KB Output is correct
27 Correct 263 ms 85984 KB Output is correct
28 Correct 264 ms 85988 KB Output is correct
29 Correct 4962 ms 100688 KB Output is correct
30 Execution timed out 5048 ms 97948 KB Time limit exceeded
31 Halted 0 ms 0 KB -