Submission #292166

#	Time	Username	Problem	Language	Result	Execution time	Memory
292166		TadijaSebez	Harvest (JOI20_harvest)	C++11	100 / 100	4216 ms	290000 KiB

harvest

#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;
}
namespace Treap{
	const int M=N*20;
	mt19937 rng(time(0));
	int ls[M],rs[M],tsz,sz[M],pri[M];
	ll key[M];
	void pull(int c){sz[c]=sz[ls[c]]+1+sz[rs[c]];}
	int make(ll x){tsz++;sz[tsz]=1;key[tsz]=x;pri[tsz]=rng();return tsz;}
	void rot_l(int&c){int a=rs[c],b=ls[a];rs[c]=b;ls[a]=c;pull(c);pull(a);c=a;}
	void rot_r(int&c){int a=ls[c],b=rs[a];ls[c]=b;rs[a]=c;pull(c);pull(a);c=a;}
	void Ins(int&c,ll x){
		if(!c)c=make(x);
		else if(key[c]<x){
			Ins(rs[c],x);
			if(pri[rs[c]]>pri[c])rot_l(c);
			else pull(c);
		}else{
			Ins(ls[c],x);
			if(pri[ls[c]]>pri[c])rot_r(c);
			else pull(c);
		}
	}
	int Lo(int c,ll x){
		if(!c)return 0;
		if(key[c]<=x)return Lo(rs[c],x)+sz[ls[c]]+1;
		else return Lo(ls[c],x);
	}
}
const int M=2*N;
int ls[M],rs[M],tsz,root,sz[M];
int treap[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;
	Treap::Ins(treap[c],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)return Treap::Lo(treap[c],y);
	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 (stderr)

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:54:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |  int mid=ss+se>>1;
      |          ~~^~~
harvest.cpp: In function 'int GetCnt(int, int, int, int, int)':
harvest.cpp:61:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |  int mid=ss+se>>1;
      |          ~~^~~
harvest.cpp: In function 'long long int Get(int, int, int, int, int)':
harvest.cpp:67:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |  int mid=ss+se>>1;
      |          ~~^~~
harvest.cpp: In function 'int Lo(int, int, int, int, int, long long int)':
harvest.cpp:73:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |  int mid=ss+se>>1;
      |          ~~^~~
harvest.cpp: In function 'int main()':
harvest.cpp:149: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]
  149 |   while(j<leaf.size()&&leaf[j].first<=T[i])Add(leaf[j]),j++;
      |         ~^~~~~~~~~~~~
harvest.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |  scanf("%i %i %i %i",&n,&m,&l,&c);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:86:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |  for(int i=1;i<=n;i++)scanf("%i",&a[i]),a[i]=l-a[i];
      |                       ~~~~~^~~~~~~~~~~~
harvest.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |   scanf("%i",&b[i]);
      |   ~~~~~^~~~~~~~~~~~
harvest.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  139 |  scanf("%i",&q);
      |  ~~~~~^~~~~~~~~
harvest.cpp:141:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  141 |   scanf("%i %lld",&V[i],&T[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 75 / 75