oj.uz

답안 #291831

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
291831 2020-09-05T20:35:15 Z TadijaSebez 수확 (JOI20_harvest) C++11
0 / 100
 3214 ms 143776 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*2;
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;
		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=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:135: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]
  135 |   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:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |   scanf("%i",&b[i]);
      |   ~~~~~^~~~~~~~~~~~
harvest.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  125 |  scanf("%i",&q);
      |  ~~~~~^~~~~~~~~
harvest.cpp:127:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |   scanf("%i %lld",&V[i],&T[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 113272 KB Output is correct
2 Correct 88 ms 118008 KB Output is correct
3 Correct 177 ms 118264 KB Output is correct
4 Correct 88 ms 117624 KB Output is correct
5 Correct 89 ms 118136 KB Output is correct
6 Correct 88 ms 118136 KB Output is correct
7 Correct 97 ms 118264 KB Output is correct
8 Correct 87 ms 118012 KB Output is correct
9 Correct 81 ms 115960 KB Output is correct
10 Correct 88 ms 118028 KB Output is correct
11 Correct 81 ms 115960 KB Output is correct
12 Correct 80 ms 115960 KB Output is correct
13 Incorrect 176 ms 118008 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3214 ms 125768 KB Output is correct
2 Incorrect 485 ms 143776 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 113272 KB Output is correct
2 Correct 88 ms 118008 KB Output is correct
3 Correct 177 ms 118264 KB Output is correct
4 Correct 88 ms 117624 KB Output is correct
5 Correct 89 ms 118136 KB Output is correct
6 Correct 88 ms 118136 KB Output is correct
7 Correct 97 ms 118264 KB Output is correct
8 Correct 87 ms 118012 KB Output is correct
9 Correct 81 ms 115960 KB Output is correct
10 Correct 88 ms 118028 KB Output is correct
11 Correct 81 ms 115960 KB Output is correct
12 Correct 80 ms 115960 KB Output is correct
13 Incorrect 176 ms 118008 KB Output isn't correct
14 Halted 0 ms 0 KB -