oj.uz

답안 #291841

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
291841 2020-09-05T20:51:15 Z TadijaSebez 수확 (JOI20_harvest) C++11
0 / 100
 3207 ms 163336 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=upper_bound(a+1,a+1+n,a[i]-c%l)-a-1;
		if(j<1){
			j=upper_bound(a+1,a+1+n,a[i]-c%l+l)-a-1;
			len[i]=a[i]+l-a[j]+c/l*l;
		}else len[i]=a[i]-a[j]+c/l*l;
		go[i]=j;
		//int j=lower_bound(a+i,a+i+1+n,a[i]+c%l)-a;
		//assert(j<=2*n);
		//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=upper_bound(a+1,a+1+n,b[i])-a-1;
		if(j==0)j=n,len[n+i]=b[i]+l-a[j];
		else len[n+i]=b[i]-a[j];
		go[n+i]=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:142: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]
  142 |   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:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |   scanf("%i",&b[i]);
      |   ~~~~~^~~~~~~~~~~~
harvest.cpp:132:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  132 |  scanf("%i",&q);
      |  ~~~~~^~~~~~~~~
harvest.cpp:134:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  134 |   scanf("%i %lld",&V[i],&T[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 56960 KB Output is correct
2 Correct 58 ms 61688 KB Output is correct
3 Correct 143 ms 61688 KB Output is correct
4 Correct 56 ms 61304 KB Output is correct
5 Correct 55 ms 61816 KB Output is correct
6 Correct 58 ms 61816 KB Output is correct
7 Correct 55 ms 61816 KB Output is correct
8 Correct 54 ms 61560 KB Output is correct
9 Correct 47 ms 59512 KB Output is correct
10 Correct 53 ms 61560 KB Output is correct
11 Correct 48 ms 59520 KB Output is correct
12 Correct 49 ms 59640 KB Output is correct
13 Incorrect 143 ms 61696 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3207 ms 69500 KB Output is correct
2 Runtime error 357 ms 163336 KB Execution killed with signal 8
3 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 56960 KB Output is correct
2 Correct 58 ms 61688 KB Output is correct
3 Correct 143 ms 61688 KB Output is correct
4 Correct 56 ms 61304 KB Output is correct
5 Correct 55 ms 61816 KB Output is correct
6 Correct 58 ms 61816 KB Output is correct
7 Correct 55 ms 61816 KB Output is correct
8 Correct 54 ms 61560 KB Output is correct
9 Correct 47 ms 59512 KB Output is correct
10 Correct 53 ms 61560 KB Output is correct
11 Correct 48 ms 59520 KB Output is correct
12 Correct 49 ms 59640 KB Output is correct
13 Incorrect 143 ms 61696 KB Output isn't correct
14 Halted 0 ms 0 KB -