Submission #216316

#	Time	Username	Problem	Language	Result	Execution time	Memory
216316		model_code	Harvest (JOI20_harvest)	C++17	100 / 100	1183 ms	100932 KiB

harvest

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>

class Segment_Tree{
	public:
	int n;
	std::vector<long long> data;
	void Init(int n_){
		n=1;
		while(n<n_) n*=2;
		data=std::vector<long long>(2*n-1);
	}
	void Update(int k){
		k+=n-1;
		data[k]++;
		while(k>0){
			k=(k-1)/2;
			data[k]=data[k*2+1]+data[k*2+2];
		}
	}
	long long Query(int a,int b){
		a+=n-1;b+=n-1;
		long long m=0;
		while(a<b){
			if(a%2==0) m+=data[a++];
			if(b%2==0) m+=data[--b];
			a/=2;b/=2;
		}
		return m;
	}
};

int N,M,L,C,Q;
std::vector<int> A;

std::vector<int> nx,right;
std::vector<std::vector<int>> rev;
std::vector<long long> cost;
std::vector<std::vector<long long>> a;
std::vector<std::vector<std::pair<long long,int>>> c;

void dfs(int v,long long dep,int rt,int &id,std::vector<std::pair<long long,std::pair<int,int>>> &query){
	int pre=id;
	for(auto i:a[v]){
		a[nx[rt]].push_back(i+dep+cost[rt]);
		query.push_back(std::make_pair(i+dep,std::make_pair(-1,id)));
	}
	for(auto p:c[v]) query.push_back(std::make_pair(p.first+dep,std::make_pair(p.second,id)));
	for(auto u:rev[v]){
		id++;
		dfs(u,dep+cost[u],rt,id,query);
	}
	right[pre]=id;
}

int main(){
	scanf("%d%d%d%d",&N,&M,&L,&C);
	A=std::vector<int>(N);
	for(int i=0;i<N;i++) scanf("%d",&A[i]);
	int id=0;
	right=nx=std::vector<int>(N);
	rev=std::vector<std::vector<int>>(N);
	cost=std::vector<long long>(N);
	a=std::vector<std::vector<long long>>(N);
	std::vector<int> deg(N),vis(N);
	for(int i=0;i<N;i++){
		int x=(A[i]-C%L+L)%L;
		auto it=std::upper_bound(A.begin(),A.end(),x);
		nx[i]=(it==A.begin()?N-1:it-A.begin()-1);
		rev[nx[i]].push_back(i);
		cost[i]=C+(x-A[nx[i]]+L)%L;
		deg[nx[i]]++;
	}
	std::queue<int> que;
	for(int i=0;i<N;i++) if(!deg[i]) que.push(i);
	while(!que.empty()){
		int v=que.front(),u=nx[v];
		que.pop();
		deg[u]--;
		if(!deg[u]) que.push(u);
	}
	for(int i=0;i<M;i++){
		int x;
		scanf("%d",&x);
		while(id<N&&A[id]<x) id++;
		int v=(id-1+N)%N;
		long long t=(x-A[v]+L)%L;
		a[v].push_back(t);
	}
	scanf("%d",&Q);
	std::vector<long long> res(Q);
	c=std::vector<std::vector<std::pair<long long,int>>>(N);
	for(int i=0;i<Q;i++){
		int v;
		long long t;
		scanf("%d%lld",&v,&t);
		v--;
		c[v].push_back(std::make_pair(t,i));
	}
	for(int i=0;i<N;i++) if(!vis[i]&&deg[i]){
		int v=i;
		long long cycle=0,dis=0;
		Segment_Tree st;
		do{
			cycle+=cost[v];
			vis[v]++;
			for(auto j:rev[v]) if(!deg[j]){
				std::vector<std::pair<long long,std::pair<int,int>>> query;
				int sz=0;
				dfs(j,0,j,sz,query);
				std::sort(query.begin(),query.end());
				st.Init(sz+1);
				for(auto pp:query){
					auto p=pp.second;
					int ind=p.second;
					if(p.first>=0) res[p.first]=st.Query(ind,right[ind]+1);
					else st.Update(ind);
				}
			}
			v=nx[v];
		}while(v!=i);
		std::vector<std::pair<long long,int>> query;
		std::vector<long long> b;
		std::map<long long,int> mp;
		do{
			for(auto j:a[v]){
				query.push_back(std::make_pair(j-dis+cycle,-1));
				b.push_back((j-dis+cycle)%cycle);
			}
			for(auto p:c[v]) if(p.first>=dis){
				query.push_back(std::make_pair(p.first-dis,p.second));
				b.push_back((p.first-dis)%cycle);
			}
			dis+=cost[v];
			v=nx[v];
		}while(v!=i);
		std::sort(query.begin(),query.end());
		std::sort(b.begin(),b.end());
		b.erase(std::unique(b.begin(),b.end()),b.end());
		int sz=b.size();
		for(int i=0;i<sz;i++) mp[b[i]]=i;
		st.Init(sz);
		long long sum=0;
		for(auto p:query){
			int j=mp[p.first%cycle];
			long long tmp=p.first/cycle;
			if(p.second>=0) res[p.second]=st.Query(0,j+1)*(tmp+1)+st.Query(j+1,sz)*tmp-sum;
			else{
				st.Update(j);
				sum+=tmp;
			}
		}
		b.clear();
		mp.clear();
		dis=0;
		do{
			for(auto j:a[v]) b.push_back(j-dis);
			for(auto p:c[v]) b.push_back(p.first-dis);
			dis+=cost[v];
			v=nx[v];
		}while(v!=i);
		std::sort(b.begin(),b.end());
		b.erase(std::unique(b.begin(),b.end()),b.end());
		sz=b.size();
		for(int i=0;i<sz;i++) mp[b[i]]=i;
		st.Init(sz);
		dis=0;
		do{
			for(auto j:a[v]) st.Update(mp[j-dis]);
			for(auto p:c[v]){
				res[p.second]+=st.Query(0,mp[p.first-dis]+1);
			}
			dis+=cost[v];
			v=nx[v];
		}while(v!=i);
	}
	for(int i=0;i<Q;i++) printf("%lld\n",res[i]);
}

Compilation message (stderr)

harvest.cpp: In function 'int main()':
harvest.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&N,&M,&L,&C);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:62:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<N;i++) scanf("%d",&A[i]);
                       ~~~~~^~~~~~~~~~~~
harvest.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~
harvest.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&Q);
  ~~~~~^~~~~~~~~
harvest.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%lld",&v,&t);
   ~~~~~^~~~~~~~~~~~~~~~

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