oj.uz

Submission #544223

# Submission time Handle Problem Language Result Execution time Memory
544223 2022-04-01T12:24:26 Z Antekb Fire (JOI20_ho_t5) C++14
6 / 100
 1000 ms 19392 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("trapv")
#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 3 ms 3412 KB Output is correct
2 Incorrect 4 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 3 ms 3412 KB Output is correct
2 Execution timed out 1081 ms 19272 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 18440 KB Output is correct
2 Correct 444 ms 18500 KB Output is correct
3 Correct 460 ms 18864 KB Output is correct
4 Correct 459 ms 18608 KB Output is correct
5 Correct 452 ms 18472 KB Output is correct
6 Correct 450 ms 18436 KB Output is correct
7 Correct 453 ms 18668 KB Output is correct
8 Correct 469 ms 18616 KB Output is correct
9 Correct 459 ms 18488 KB Output is correct
10 Correct 446 ms 18732 KB Output is correct
11 Correct 466 ms 18628 KB Output is correct
12 Correct 466 ms 18632 KB Output is correct
13 Correct 457 ms 18620 KB Output is correct
14 Correct 475 ms 18608 KB Output is correct

Subtask #5
0 / 80.0

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