oj.uz

Submission #292160

# Submission time Handle Problem Language Result Execution time Memory
292160 2020-09-06T13:04:57 Z TadijaSebez Harvest (JOI20_harvest) C++11
5 / 100
 3232 ms 164728 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],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 40 ms 56952 KB Output is correct
2 Correct 58 ms 61688 KB Output is correct
3 Correct 148 ms 61756 KB Output is correct
4 Correct 56 ms 61176 KB Output is correct
5 Correct 58 ms 61816 KB Output is correct
6 Correct 56 ms 61944 KB Output is correct
7 Correct 56 ms 61944 KB Output is correct
8 Correct 62 ms 61688 KB Output is correct
9 Correct 50 ms 59640 KB Output is correct
10 Correct 55 ms 61688 KB Output is correct
11 Correct 51 ms 59640 KB Output is correct
12 Correct 51 ms 59768 KB Output is correct
13 Correct 128 ms 61816 KB Output is correct
14 Correct 98 ms 61816 KB Output is correct
15 Correct 61 ms 61816 KB Output is correct
16 Correct 58 ms 61816 KB Output is correct
17 Correct 57 ms 61816 KB Output is correct
18 Correct 56 ms 61720 KB Output is correct
19 Correct 55 ms 61720 KB Output is correct
20 Correct 56 ms 61816 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3232 ms 69480 KB Output is correct
2 Runtime error 355 ms 164728 KB Execution killed with signal 8
3 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 56952 KB Output is correct
2 Correct 58 ms 61688 KB Output is correct
3 Correct 148 ms 61756 KB Output is correct
4 Correct 56 ms 61176 KB Output is correct
5 Correct 58 ms 61816 KB Output is correct
6 Correct 56 ms 61944 KB Output is correct
7 Correct 56 ms 61944 KB Output is correct
8 Correct 62 ms 61688 KB Output is correct
9 Correct 50 ms 59640 KB Output is correct
10 Correct 55 ms 61688 KB Output is correct
11 Correct 51 ms 59640 KB Output is correct
12 Correct 51 ms 59768 KB Output is correct
13 Correct 128 ms 61816 KB Output is correct
14 Correct 98 ms 61816 KB Output is correct
15 Correct 61 ms 61816 KB Output is correct
16 Correct 58 ms 61816 KB Output is correct
17 Correct 57 ms 61816 KB Output is correct
18 Correct 56 ms 61720 KB Output is correct
19 Correct 55 ms 61720 KB Output is correct
20 Correct 56 ms 61816 KB Output is correct
21 Correct 3232 ms 69480 KB Output is correct
22 Runtime error 355 ms 164728 KB Execution killed with signal 8
23 Halted 0 ms 0 KB -