Submission #445408

#	Time	Username	Problem	Language	Result	Execution time	Memory
445408		kig9981	Harvest (JOI20_harvest)	C++17	100 / 100	999 ms	107640 KiB

harvest

#include <bits/stdc++.h>
#include <bits/extc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

typedef __gnu_pbds::tree<pair<long long,int>,__gnu_pbds::null_type,less<pair<long long,int>>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update> ordered_set;
ordered_set S[200000];
vector<pair<long long,int>> qry[200000];
int A[200000], P[200000], cnt[200000], R[200000], PW[200000];
long long ans[200000], O[200000];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M, L, C;
	queue<int> Q;
	cin>>N>>M>>L>>C;
	for(int i=0;i<N;i++) cin>>A[R[i]=i];
	for(int i=0;i<N;i++) {
		cnt[P[i]=(upper_bound(A,A+N,(L+(A[i]-C)%L)%L)-A+N-1)%N]++;
		PW[i]=C+(L+(A[i]+3LL*L-A[P[i]]-C)%L)%L;
	}
	for(int i=0;i<M;i++) {
		int b, p;
		cin>>b;
		p=(upper_bound(A,A+N,b)-A+N-1)%N;
		S[p].insert({(b-A[p]+L)%L,i});
	}
	cin>>M;
	for(int i=0;i<M;i++) {
		int v;
		long long t;
		cin>>v>>t;
		qry[--v].emplace_back(t,i);
	}
	for(int i=0;i<N;i++) if(cnt[i]==0) Q.push(i);
	while(!Q.empty()) {
		int c=Q.front();
		Q.pop();
		for(auto[t,i]: qry[c]) ans[i]=S[R[c]].order_of_key({t+1-O[c],0});
		O[c]+=PW[c];
		if(S[R[P[c]]].size()<S[R[c]].size()) {
			swap(R[c],R[P[c]]);
			swap(O[c],O[P[c]]);
		}
		for(auto[t,i]: S[R[c]]) S[R[P[c]]].insert({t+O[c]-O[P[c]],i});
		if(--cnt[P[c]]==0) Q.push(P[c]);
	}
	for(int r=0;r<N;r++) if(cnt[r]) {
		vector<int> V;
		ordered_set C;
		long long tot=PW[r], sum=PW[r];
		V.push_back(r); cnt[r]=0;
		for(auto[t,j]: S[R[r]]) C.insert({t+O[r],j});
		for(int i=P[r];cnt[i];i=P[i]) {
			V.push_back(i);
			cnt[i]=0;
			tot+=PW[i];
		}
		for(int i=1;i<V.size();i++) {
			for(auto[t,j]: S[R[V[i]]]) C.insert({t+tot-sum+O[V[i]],j});
			sum+=PW[V[i]];
		}
		sum=0;
		for(auto v: V) {
			for(auto[t,i]: qry[v]) {
				long long rd=t%tot;
				ans[i]=(t/tot+1)*C.order_of_key({rd+1-sum,0});
				for(int m=0;C.size() && m*tot+rd-sum<=C.rbegin()->first;m++) ans[i]+=max(t/tot-m,0LL)*(C.order_of_key({(m+1)*tot+rd+1-sum,0})-C.order_of_key({m*tot+rd+1-sum,0}));
			}
			sum+=PW[v];
			for(auto[t,i]: S[R[P[v]]]) {
				C.erase({t+O[P[v]]+tot-sum,i});
				C.insert({t+O[P[v]]-sum,i});
			}
		}
	}
	for(int i=0;i<M;i++) cout<<ans[i]<<'\n';
	return 0;
}

Compilation message (stderr)

harvest.cpp: In function 'int main()':
harvest.cpp:72:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int i=1;i<V.size();i++) {
      |               ~^~~~~~~~~

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