oj.uz

Submission #544222

# Submission time Handle Problem Language Result Execution time Memory
544222 2022-04-01T12:23:29 Z Antekb Fire (JOI20_ho_t5) C++14
6 / 100
 1000 ms 19824 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
using ll = long long;
const int N=1<<18;
int tab[N], L[N], R[N];
int ile[N+N];
ll sum[N+N];
set<int> S;
int n;
int pra(int i){
	//cout<<i<<" "<<ile[n+N+1]<<endl;
	//assert(ile[N+n+1]);
	for(i+=N; i>0; i/=2){
		if((i&1)==0 && ile[i+1]){
			i++;
			while(i<N){
				if(ile[i+i])i=i+i;
				else i=i+i+1;
			}
			//cout<<"? "<<i-N<<endl;
			return i-N;
		}
	}
	assert(false);
	return 0;
}
int lew(int i){
	for(i+=N; i>0; i/=2){
		if((i&1) && ile[i-1]){
			i--;
			while(i<N){
				if(ile[i+i+1])i=i+i+1;
				else i=i+i;
			}
			//cout<<"? "<<i-N<<endl;
			return i-N;
		}
	}
	assert(false);
	return 0;
}
void upd(int i){
	if(i==0 || i==n+1)return;
	//cout<<i<<"u"<<endl;
	if(S.find(i)!=S.end())S.erase(S.find(i));
	//cout<<i<<"a"<<lew(i)<<" "<<tab[lew(i)]<<" "<<tab[i]<<"\n";
	L[i]=(tab[lew(i)]>tab[i]);
	R[i]=(tab[pra(i)]<tab[i]);
	if(L[i]^R[i]){
		S.insert(i);
	}
	//cout<<i<<"u"<<endl;
}
void usun(int i){
	//cout<<"- "<<i<<endl;
	int ii=i;
	for(i+=N; i>0; i>>=1){
		sum[i]-=tab[ii];
		ile[i]--;
		assert(ile[i]>=0);
	}
	upd(lew(ii));
	upd(pra(ii));
	if(S.find(ii)!=S.end())S.erase(S.find(ii));
}
void dodaj(int i){
	int ii=i;
	for(i+=N; i>0; i>>=1){
		sum[i]+=tab[ii];
		ile[i]++;
	}
}
ll quer(int k){
	ll ans=0;
	int v=1;
	while(v<N){
		if(ile[v+v]<=k){
			k-=ile[v+v];
			ans+=sum[v+v];
			v=v+v+1;
		}
		else v=v+v;
	}
	assert(k<=ile[v]);
	if(k)ans+=k*1ll*tab[v-N];
	return ans;
}
int main(){
	int q;
	cin>>n>>q;
	tab[0]=0;
	ile[N]=1;
	for(int i=1; i<=n; i++){
		cin>>tab[i];
		ile[N+i]=1;
		sum[N+i]=tab[i];
	}
	tab[n+1]=1e9+5;
	ile[n+1+N]=1;
	for(int i=N-1; i>0; i--){
		ile[i]=ile[i+i]+ile[i+i+1];
		sum[i]=sum[i+i]+sum[i+i+1];
	}
	for(int i=1; i<=n; i++){
		upd(i);
		//cout<<L[i]<<" "<<R[i]<<"\n";
	}
	vector<pair<pair<int, int>, pair<int, int> > > Q(q);
	for(int i=0; i<q; i++){
		Q[i].st.nd=i;
		cin>>Q[i].st.st>>Q[i].nd.st>>Q[i].nd.nd;
		Q[i].nd.nd++;
	}
	vector<ll> ans(q);
	sort(Q.begin(), Q.end());
	int wsk=0;
	//assert(S.find(0)==S.end());
	for(int t=1; t<=n; t++){
		//cout<<t<<"aaa"<<endl;
		vector<int> V, V2;
		for(auto it=S.begin(); it!=S.end(); it++){
			//cout<<*it<<"\n";
			//V.push_back(*it);
			if(L[*it])V.push_back(*it);
			else V2.push_back(*it);
		}
		/*for(int i:V)
		{
			//assert(i!=0);
			if(L[i]){
				//cout<<"- "<<i<<endl;
				usun(i);
			}
			else{
				//cout<<"+ "<<i<<endl;
				dodaj(i);
			}
		}*/
		for(int i:V2)dodaj(i);
		for(int i:V)usun(i);
		//return 0;
		/*if(t==1){
			cout<<quer(1)<<" "<<quer(2)<<" "<<quer(3)<<" "<<quer(4)<<"\n";
		}*/
		while(wsk<q && Q[wsk].st.st==t){
			ans[Q[wsk].st.nd]=quer(Q[wsk].nd.nd)-quer(Q[wsk].nd.st);
			wsk++;
		}
	}
	for(int i=0; i<q; i++)cout<<ans[i]<<"\n";
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Incorrect 3 ms 3412 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Execution timed out 1083 ms 19552 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Execution timed out 1073 ms 19824 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 18932 KB Output is correct
2 Correct 369 ms 18832 KB Output is correct
3 Correct 384 ms 19256 KB Output is correct
4 Correct 374 ms 18936 KB Output is correct
5 Correct 378 ms 18888 KB Output is correct
6 Correct 369 ms 18892 KB Output is correct
7 Correct 375 ms 19180 KB Output is correct
8 Correct 376 ms 19028 KB Output is correct
9 Correct 373 ms 18920 KB Output is correct
10 Correct 374 ms 19116 KB Output is correct
11 Correct 373 ms 19060 KB Output is correct
12 Correct 376 ms 19144 KB Output is correct
13 Correct 393 ms 19016 KB Output is correct
14 Correct 381 ms 19084 KB Output is correct

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Incorrect 3 ms 3412 KB Output isn't correct
3 Halted 0 ms 0 KB -