oj.uz

Submission #291820

# Submission time Handle Problem Language Result Execution time Memory
291820 2020-09-05T20:16:49 Z TadijaSebez Harvest (JOI20_harvest) C++11
0 / 100
 3174 ms 164856 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];
	//printf("%i dep %lld\n",u,dep[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<int> ost[M];
ll sub[M];
void Set(int&c,int ss,int se,int qi,ll x,int 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,int 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,int 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];
		//printf("(%i -> %i) %i\n",i,go[i],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;
		//printf("[ ");
		do{
			chn.pb(k);
			//printf("%i ",k);
			on_chn[k]=on_chn[k+h]=1;
			chn_len[csz]+=len[k];
			k=go[k];
		}while(k!=j);
		//printf(" ]\n");
		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:14:8: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   14 |  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, int)':
harvest.cpp:28:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |  int mid=ss+se>>1;
      |          ~~^~~
harvest.cpp: In function 'int GetCnt(int, int, int, int, int)':
harvest.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |  int mid=ss+se>>1;
      |          ~~^~~
harvest.cpp: In function 'long long int Get(int, int, int, int, int)':
harvest.cpp:41:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |  int mid=ss+se>>1;
      |          ~~^~~
harvest.cpp: In function 'int Lo(int, int, int, int, int, int)':
harvest.cpp:54:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |  int mid=ss+se>>1;
      |          ~~^~~
harvest.cpp: In function 'int main()':
harvest.cpp:134: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]
  134 |   while(j<leaf.size()&&leaf[j].first<=T[i])Add(leaf[j]),j++;
      |         ~^~~~~~~~~~~~
harvest.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |  scanf("%i %i %i %i",&n,&m,&l,&c);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:67:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |  for(int i=1;i<=n;i++)scanf("%i",&a[i]),a[i]=l-a[i];
      |                       ~~~~~^~~~~~~~~~~~
harvest.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |   scanf("%i",&b[i]);
      |   ~~~~~^~~~~~~~~~~~
harvest.cpp:124:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  124 |  scanf("%i",&q);
      |  ~~~~~^~~~~~~~~
harvest.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  126 |   scanf("%i %lld",&V[i],&T[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 56952 KB Output is correct
2 Correct 59 ms 61816 KB Output is correct
3 Correct 156 ms 61816 KB Output is correct
4 Correct 55 ms 61360 KB Output is correct
5 Correct 59 ms 61852 KB Output is correct
6 Correct 57 ms 61944 KB Output is correct
7 Correct 56 ms 61944 KB Output is correct
8 Correct 57 ms 61688 KB Output is correct
9 Correct 49 ms 59640 KB Output is correct
10 Correct 54 ms 61696 KB Output is correct
11 Correct 49 ms 59640 KB Output is correct
12 Correct 50 ms 59768 KB Output is correct
13 Incorrect 144 ms 61816 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3174 ms 69572 KB Output is correct
2 Runtime error 341 ms 164856 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 41 ms 56952 KB Output is correct
2 Correct 59 ms 61816 KB Output is correct
3 Correct 156 ms 61816 KB Output is correct
4 Correct 55 ms 61360 KB Output is correct
5 Correct 59 ms 61852 KB Output is correct
6 Correct 57 ms 61944 KB Output is correct
7 Correct 56 ms 61944 KB Output is correct
8 Correct 57 ms 61688 KB Output is correct
9 Correct 49 ms 59640 KB Output is correct
10 Correct 54 ms 61696 KB Output is correct
11 Correct 49 ms 59640 KB Output is correct
12 Correct 50 ms 59768 KB Output is correct
13 Incorrect 144 ms 61816 KB Output isn't correct
14 Halted 0 ms 0 KB -