oj.uz

Submission #544225

# Submission time Handle Problem Language Result Execution time Memory
544225 2022-04-01T12:35:47 Z Antekb Fire (JOI20_ho_t5) C++14
7 / 100
 1000 ms 19544 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(ile[ii+N]==0)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
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3284 KB Output is correct
2 Correct 4 ms 3412 KB Output is correct
3 Correct 4 ms 3412 KB Output is correct
4 Correct 3 ms 3412 KB Output is correct
5 Correct 3 ms 3412 KB Output is correct
6 Correct 3 ms 3412 KB Output is correct
7 Correct 4 ms 3412 KB Output is correct
8 Correct 3 ms 3376 KB Output is correct
9 Correct 3 ms 3412 KB Output is correct
10 Correct 3 ms 3412 KB Output is correct
11 Correct 3 ms 3384 KB Output is correct
12 Correct 3 ms 3412 KB Output is correct
13 Correct 3 ms 3412 KB Output is correct
14 Correct 4 ms 3412 KB Output is correct
15 Correct 4 ms 3412 KB Output is correct
16 Correct 3 ms 3412 KB Output is correct
17 Correct 3 ms 3412 KB Output is correct
18 Correct 3 ms 3376 KB Output is correct
19 Correct 4 ms 3412 KB Output is correct
20 Correct 4 ms 3412 KB Output is correct
21 Correct 3 ms 3412 KB Output is correct
22 Correct 3 ms 3412 KB Output is correct
23 Correct 3 ms 3412 KB Output is correct
24 Correct 3 ms 3412 KB Output is correct
25 Correct 3 ms 3412 KB Output is correct
26 Correct 3 ms 3412 KB Output is correct
27 Correct 3 ms 3412 KB Output is correct
28 Correct 3 ms 3380 KB Output is correct
29 Correct 4 ms 3412 KB Output is correct
30 Correct 4 ms 3380 KB Output is correct
31 Correct 3 ms 3412 KB Output is correct
32 Correct 4 ms 3412 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3284 KB Output is correct
2 Execution timed out 1092 ms 19192 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 3284 KB Output is correct
2 Execution timed out 1079 ms 19544 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 18452 KB Output is correct
2 Correct 476 ms 18500 KB Output is correct
3 Correct 498 ms 18864 KB Output is correct
4 Correct 483 ms 19120 KB Output is correct
5 Correct 503 ms 18980 KB Output is correct
6 Correct 547 ms 18992 KB Output is correct
7 Correct 551 ms 19188 KB Output is correct
8 Correct 559 ms 19196 KB Output is correct
9 Correct 504 ms 19012 KB Output is correct
10 Correct 472 ms 19108 KB Output is correct
11 Correct 506 ms 19192 KB Output is correct
12 Correct 503 ms 19168 KB Output is correct
13 Correct 526 ms 19076 KB Output is correct
14 Correct 487 ms 19168 KB Output is correct

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3284 KB Output is correct
2 Correct 4 ms 3412 KB Output is correct
3 Correct 4 ms 3412 KB Output is correct
4 Correct 3 ms 3412 KB Output is correct
5 Correct 3 ms 3412 KB Output is correct
6 Correct 3 ms 3412 KB Output is correct
7 Correct 4 ms 3412 KB Output is correct
8 Correct 3 ms 3376 KB Output is correct
9 Correct 3 ms 3412 KB Output is correct
10 Correct 3 ms 3412 KB Output is correct
11 Correct 3 ms 3384 KB Output is correct
12 Correct 3 ms 3412 KB Output is correct
13 Correct 3 ms 3412 KB Output is correct
14 Correct 4 ms 3412 KB Output is correct
15 Correct 4 ms 3412 KB Output is correct
16 Correct 3 ms 3412 KB Output is correct
17 Correct 3 ms 3412 KB Output is correct
18 Correct 3 ms 3376 KB Output is correct
19 Correct 4 ms 3412 KB Output is correct
20 Correct 4 ms 3412 KB Output is correct
21 Correct 3 ms 3412 KB Output is correct
22 Correct 3 ms 3412 KB Output is correct
23 Correct 3 ms 3412 KB Output is correct
24 Correct 3 ms 3412 KB Output is correct
25 Correct 3 ms 3412 KB Output is correct
26 Correct 3 ms 3412 KB Output is correct
27 Correct 3 ms 3412 KB Output is correct
28 Correct 3 ms 3380 KB Output is correct
29 Correct 4 ms 3412 KB Output is correct
30 Correct 4 ms 3380 KB Output is correct
31 Correct 3 ms 3412 KB Output is correct
32 Correct 4 ms 3412 KB Output is correct
33 Execution timed out 1092 ms 19192 KB Time limit exceeded
34 Halted 0 ms 0 KB -