oj.uz

Submission #544231

# Submission time Handle Problem Language Result Execution time Memory
544231 2022-04-01T12:46:17 Z Antekb Fire (JOI20_ho_t5) C++14
100 / 100
 767 ms 29972 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 pr[N], le[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;
}*/
int lew(int i){
	if(le[i]==i)return i;
	return le[i]=lew(le[i]);
}
int pra(int i){
	if(pr[i]==i)return i;
	return pr[i]=pra(pr[i]);
}
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-1)]>tab[i]);
	R[i]=(tab[pra(i+1)]<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);
	}
	if(ile[ii+N]==0){
		S.erase(S.find(ii));
		le[ii]=ii-1;
		pr[ii]=ii+1;
		upd(lew(ii-1));
		upd(pra(ii+1));
	}
}
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=0; i<=n+1; i++)le[i]=pr[i]=i;
	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 2 ms 3412 KB Output is correct
2 Correct 3 ms 3412 KB Output is correct
3 Correct 3 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 3 ms 3412 KB Output is correct
8 Correct 3 ms 3412 KB Output is correct
9 Correct 3 ms 3412 KB Output is correct
10 Correct 3 ms 3380 KB Output is correct
11 Correct 3 ms 3412 KB Output is correct
12 Correct 3 ms 3412 KB Output is correct
13 Correct 3 ms 3412 KB Output is correct
14 Correct 3 ms 3412 KB Output is correct
15 Correct 3 ms 3412 KB Output is correct
16 Correct 3 ms 3412 KB Output is correct
17 Correct 3 ms 3376 KB Output is correct
18 Correct 3 ms 3412 KB Output is correct
19 Correct 2 ms 3412 KB Output is correct
20 Correct 3 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 3384 KB Output is correct
25 Correct 3 ms 3412 KB Output is correct
26 Correct 3 ms 3420 KB Output is correct
27 Correct 3 ms 3412 KB Output is correct
28 Correct 2 ms 3380 KB Output is correct
29 Correct 2 ms 3384 KB Output is correct
30 Correct 3 ms 3412 KB Output is correct
31 Correct 3 ms 3412 KB Output is correct
32 Correct 3 ms 3412 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 596 ms 24248 KB Output is correct
3 Correct 584 ms 29068 KB Output is correct
4 Correct 598 ms 29060 KB Output is correct
5 Correct 587 ms 29556 KB Output is correct
6 Correct 566 ms 28832 KB Output is correct
7 Correct 575 ms 29196 KB Output is correct
8 Correct 605 ms 29532 KB Output is correct
9 Correct 596 ms 29288 KB Output is correct
10 Correct 575 ms 28844 KB Output is correct
11 Correct 616 ms 29532 KB Output is correct
12 Correct 582 ms 28760 KB Output is correct
13 Correct 585 ms 29388 KB Output is correct
14 Correct 599 ms 29260 KB Output is correct
15 Correct 593 ms 29412 KB Output is correct
16 Correct 580 ms 28860 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 594 ms 23384 KB Output is correct
3 Correct 602 ms 27688 KB Output is correct
4 Correct 585 ms 28916 KB Output is correct
5 Correct 573 ms 27848 KB Output is correct
6 Correct 624 ms 28012 KB Output is correct
7 Correct 623 ms 28356 KB Output is correct
8 Correct 614 ms 28080 KB Output is correct
9 Correct 588 ms 27904 KB Output is correct
10 Correct 604 ms 27560 KB Output is correct
11 Correct 585 ms 28764 KB Output is correct
12 Correct 587 ms 28384 KB Output is correct
13 Correct 595 ms 28600 KB Output is correct
14 Correct 547 ms 27984 KB Output is correct
15 Correct 611 ms 28560 KB Output is correct
16 Correct 572 ms 28336 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 20864 KB Output is correct
2 Correct 401 ms 20900 KB Output is correct
3 Correct 369 ms 21188 KB Output is correct
4 Correct 367 ms 20760 KB Output is correct
5 Correct 380 ms 20700 KB Output is correct
6 Correct 364 ms 20724 KB Output is correct
7 Correct 373 ms 20972 KB Output is correct
8 Correct 363 ms 20824 KB Output is correct
9 Correct 389 ms 20652 KB Output is correct
10 Correct 372 ms 20764 KB Output is correct
11 Correct 374 ms 20840 KB Output is correct
12 Correct 366 ms 20836 KB Output is correct
13 Correct 361 ms 20756 KB Output is correct
14 Correct 382 ms 20760 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 3 ms 3412 KB Output is correct
3 Correct 3 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 3 ms 3412 KB Output is correct
8 Correct 3 ms 3412 KB Output is correct
9 Correct 3 ms 3412 KB Output is correct
10 Correct 3 ms 3380 KB Output is correct
11 Correct 3 ms 3412 KB Output is correct
12 Correct 3 ms 3412 KB Output is correct
13 Correct 3 ms 3412 KB Output is correct
14 Correct 3 ms 3412 KB Output is correct
15 Correct 3 ms 3412 KB Output is correct
16 Correct 3 ms 3412 KB Output is correct
17 Correct 3 ms 3376 KB Output is correct
18 Correct 3 ms 3412 KB Output is correct
19 Correct 2 ms 3412 KB Output is correct
20 Correct 3 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 3384 KB Output is correct
25 Correct 3 ms 3412 KB Output is correct
26 Correct 3 ms 3420 KB Output is correct
27 Correct 3 ms 3412 KB Output is correct
28 Correct 2 ms 3380 KB Output is correct
29 Correct 2 ms 3384 KB Output is correct
30 Correct 3 ms 3412 KB Output is correct
31 Correct 3 ms 3412 KB Output is correct
32 Correct 3 ms 3412 KB Output is correct
33 Correct 596 ms 24248 KB Output is correct
34 Correct 584 ms 29068 KB Output is correct
35 Correct 598 ms 29060 KB Output is correct
36 Correct 587 ms 29556 KB Output is correct
37 Correct 566 ms 28832 KB Output is correct
38 Correct 575 ms 29196 KB Output is correct
39 Correct 605 ms 29532 KB Output is correct
40 Correct 596 ms 29288 KB Output is correct
41 Correct 575 ms 28844 KB Output is correct
42 Correct 616 ms 29532 KB Output is correct
43 Correct 582 ms 28760 KB Output is correct
44 Correct 585 ms 29388 KB Output is correct
45 Correct 599 ms 29260 KB Output is correct
46 Correct 593 ms 29412 KB Output is correct
47 Correct 580 ms 28860 KB Output is correct
48 Correct 594 ms 23384 KB Output is correct
49 Correct 602 ms 27688 KB Output is correct
50 Correct 585 ms 28916 KB Output is correct
51 Correct 573 ms 27848 KB Output is correct
52 Correct 624 ms 28012 KB Output is correct
53 Correct 623 ms 28356 KB Output is correct
54 Correct 614 ms 28080 KB Output is correct
55 Correct 588 ms 27904 KB Output is correct
56 Correct 604 ms 27560 KB Output is correct
57 Correct 585 ms 28764 KB Output is correct
58 Correct 587 ms 28384 KB Output is correct
59 Correct 595 ms 28600 KB Output is correct
60 Correct 547 ms 27984 KB Output is correct
61 Correct 611 ms 28560 KB Output is correct
62 Correct 572 ms 28336 KB Output is correct
63 Correct 360 ms 20864 KB Output is correct
64 Correct 401 ms 20900 KB Output is correct
65 Correct 369 ms 21188 KB Output is correct
66 Correct 367 ms 20760 KB Output is correct
67 Correct 380 ms 20700 KB Output is correct
68 Correct 364 ms 20724 KB Output is correct
69 Correct 373 ms 20972 KB Output is correct
70 Correct 363 ms 20824 KB Output is correct
71 Correct 389 ms 20652 KB Output is correct
72 Correct 372 ms 20764 KB Output is correct
73 Correct 374 ms 20840 KB Output is correct
74 Correct 366 ms 20836 KB Output is correct
75 Correct 361 ms 20756 KB Output is correct
76 Correct 382 ms 20760 KB Output is correct
77 Correct 584 ms 28904 KB Output is correct
78 Correct 614 ms 29400 KB Output is correct
79 Correct 622 ms 29496 KB Output is correct
80 Correct 620 ms 28960 KB Output is correct
81 Correct 584 ms 28756 KB Output is correct
82 Correct 599 ms 29112 KB Output is correct
83 Correct 758 ms 28896 KB Output is correct
84 Correct 720 ms 28916 KB Output is correct
85 Correct 752 ms 29444 KB Output is correct
86 Correct 720 ms 28972 KB Output is correct
87 Correct 765 ms 29848 KB Output is correct
88 Correct 767 ms 29644 KB Output is correct
89 Correct 743 ms 28788 KB Output is correct
90 Correct 753 ms 29536 KB Output is correct
91 Correct 675 ms 28784 KB Output is correct
92 Correct 614 ms 28664 KB Output is correct
93 Correct 660 ms 28944 KB Output is correct
94 Correct 739 ms 29972 KB Output is correct
95 Correct 723 ms 29788 KB Output is correct
96 Correct 668 ms 29100 KB Output is correct
97 Correct 659 ms 29100 KB Output is correct
98 Correct 697 ms 28488 KB Output is correct
99 Correct 655 ms 28668 KB Output is correct
100 Correct 640 ms 28900 KB Output is correct
101 Correct 641 ms 28668 KB Output is correct
102 Correct 624 ms 29528 KB Output is correct