oj.uz

Submission #967737

# Submission time Handle Problem Language Result Execution time Memory
967737 2024-04-22T17:38:49 Z amirhoseinfar1385 Fire (JOI20_ho_t5) C++17
100 / 100
 628 ms 137420 KB 
#include<bits/stdc++.h>
using namespace std;
const long long maxn=400000+10;
struct fenwick{
	long long fn[maxn];
	void clear(){
		for(long long i=0;i<maxn;i++){
			fn[i]=0;
		}
	}
	void upd(long long l,long long r,long long w){
		//cout<<"upd: "<<l<<" "<<r<<" "<<w<<endl;
		l++;
		r++;
		if(l>r){
			return ;
		}
		r++;
		while(l<maxn){
			fn[l]+=w;
			l+=((-l)&l);
		}
		while(r<maxn){
			fn[r]-=w;
			r+=((-r)&r);
		}
	}
	long long pors(long long i){
		long long ret=0;
		i++;
		while(i>0){
			ret+=fn[i];
			i-=((-i)&i);
		}
		return ret;
	}
}sumw,sumwe;
struct que{
	long long ind,l,r;
}allq[maxn];
struct ezaf{
	long long sot,pa,tp,w;
	long long qq,radif,soton,z;
	ezaf(){
		qq=-1;
	}
};
long long n,q;
long long all[maxn],dpl[maxn],dpr[maxn],res[maxn];
vector<ezaf>amood,mov;

void vorod(){
	cin>>n>>q;
	for(long long i=1;i<=n;i++){
		cin>>all[i];
	}
	for(long long i=1;i<=q;i++){
		cin>>allq[i].ind>>allq[i].l>>allq[i].r;
	}
}

void caldp(){
	vector<long long>v;
	for(long long i=1;i<=n;i++){
		while((long long)v.size()>0&&all[v.back()]<=(long long)all[i]){
			v.pop_back();
		}
		if((long long)v.size()==0){
			dpl[i]=-1;
		}else{
			dpl[i]=v.back();
		}
		v.push_back(i);
	}
	v.clear();
	for(long long i=n;i>=1;i--){
		while((long long)v.size()>0&&all[v.back()]<(long long)all[i]){
			v.pop_back();
		}
		if((long long)v.size()==0){
			dpr[i]=-1;
		}else{
			dpr[i]=v.back();
		}
		v.push_back(i);
	}
}

void pre(){
	caldp();
	for(long long i=1;i<=q;i++){
		ezaf e;
		e.qq=i;
		e.radif=allq[i].ind;
		e.soton=allq[i].l-1;
		e.z=-1;
		amood.push_back(e);
		mov.push_back(e);
		e.soton=allq[i].r;
		e.z=1;
		amood.push_back(e);
		mov.push_back(e);
	}
	for(long long i=1;i<=n;i++){
		long long lenamood,lenmov;
		if(dpl[i]==-1){
			lenamood=n+5;
		}else{
			lenamood=i-dpl[i];
		}
		if(dpr[i]==-1){
			lenmov=n+5;
		}else{
			lenmov=dpr[i]-i;
		}
		////cout<<"chy: "<<i<<" "<<lenamood<<" "<<lenmov<<endl;
		ezaf e;
		e.sot=i;
		e.pa=0;
		e.tp=lenamood-2;
		e.w=all[i];
		amood.push_back(e);
		e.pa=lenamood-1;
		e.tp=lenamood-1+lenmov-1;
		mov.push_back(e);
		e.sot=i+1;
		e.pa=0;
		e.tp=lenmov-2;
		e.w=-all[i];
		mov.push_back(e);
		e.sot=i+1+lenmov-2+1;
		e.pa=lenmov-2+1;
		e.tp=e.pa+lenamood-1;
		amood.push_back(e);
	}
}

bool cmpamood(ezaf a,ezaf b){
	long long la,lb;
	if(a.qq==-1){
		la=a.sot;
	}else{
		la=a.soton;
	}
	if(b.qq==-1){
		lb=b.sot;
	}else{
		lb=b.soton;
	}
	if(la==lb){
		return a.qq<b.qq;
	}
	return la<lb;
}

bool cmpmov(ezaf a,ezaf b){
	long long la,lb;
	if(a.qq==-1){
		la=a.sot-a.pa;
	}else{
		la=a.soton-a.radif;
	}
	if(b.qq==-1){
		lb=b.sot-b.pa;
	}else{
		lb=b.soton-b.radif;
	}
	if(la==lb){
		return a.qq<b.qq;
	}
	return la<lb;
}

void solve(){
	sort(amood.begin(),amood.end(),cmpamood);
	sort(mov.begin(),mov.end(),cmpmov);
	for(auto x:amood){
		if(x.qq==-1){
		//	//cout<<"wtf: "<<x.w<<endl;
			sumw.upd(x.pa,x.tp,x.w);
			sumwe.upd(x.pa,x.tp,-x.w*(x.sot-1));
		}else{
			//cout<<"pors: "<<x.qq<<" "<<x.radif<<" "<<x.soton<<endl;
			long long fake=sumw.pors(x.radif)*x.soton+sumwe.pors(x.radif);
			res[x.qq]+=fake*x.z;
		}
	}
	sumw.clear();
	sumwe.clear();
	for(auto x:mov){
		if(x.qq==-1){
			////cout<<"wtf: "<<x.sot<<" "<<x.pa<<" "<<x.tp<<endl;
			//cout<<x.sot<<" hey:"<<endl;
			sumw.upd(x.pa,x.tp,x.w);
			sumwe.upd(x.pa,x.tp,-x.w*(x.sot-x.pa-1));
		}else{
			//cout<<"pors: "<<x.qq<<" "<<x.radif<<" "<<x.soton<<endl;
			long long fake=sumw.pors(x.radif)*(x.soton-x.radif)+sumwe.pors(x.radif);
			res[x.qq]+=fake*x.z;
		}
	}
}

void khor(){
	for(long long i=1;i<=q;i++){
		cout<<res[i]<<"\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	pre();
	solve();
	khor();
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 5 ms 14940 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 5 ms 15056 KB Output is correct
6 Correct 3 ms 16216 KB Output is correct
7 Correct 4 ms 14940 KB Output is correct
8 Correct 3 ms 16220 KB Output is correct
9 Correct 3 ms 16220 KB Output is correct
10 Correct 4 ms 14940 KB Output is correct
11 Correct 3 ms 16336 KB Output is correct
12 Correct 4 ms 14940 KB Output is correct
13 Correct 3 ms 16220 KB Output is correct
14 Correct 4 ms 14980 KB Output is correct
15 Correct 4 ms 14940 KB Output is correct
16 Correct 3 ms 16220 KB Output is correct
17 Correct 3 ms 14940 KB Output is correct
18 Correct 4 ms 14940 KB Output is correct
19 Correct 4 ms 14940 KB Output is correct
20 Correct 4 ms 14940 KB Output is correct
21 Correct 3 ms 16220 KB Output is correct
22 Correct 4 ms 16216 KB Output is correct
23 Correct 4 ms 14940 KB Output is correct
24 Correct 4 ms 14940 KB Output is correct
25 Correct 3 ms 16220 KB Output is correct
26 Correct 3 ms 16220 KB Output is correct
27 Correct 4 ms 15008 KB Output is correct
28 Correct 4 ms 14936 KB Output is correct
29 Correct 4 ms 14940 KB Output is correct
30 Correct 3 ms 16344 KB Output is correct
31 Correct 5 ms 14940 KB Output is correct
32 Correct 3 ms 16220 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 592 ms 133704 KB Output is correct
3 Correct 534 ms 134480 KB Output is correct
4 Correct 581 ms 134748 KB Output is correct
5 Correct 555 ms 134716 KB Output is correct
6 Correct 584 ms 131820 KB Output is correct
7 Correct 563 ms 134440 KB Output is correct
8 Correct 578 ms 134832 KB Output is correct
9 Correct 589 ms 134444 KB Output is correct
10 Correct 565 ms 134488 KB Output is correct
11 Correct 561 ms 136912 KB Output is correct
12 Correct 546 ms 132188 KB Output is correct
13 Correct 586 ms 135568 KB Output is correct
14 Correct 569 ms 134500 KB Output is correct
15 Correct 618 ms 134472 KB Output is correct
16 Correct 582 ms 133200 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 576 ms 134112 KB Output is correct
3 Correct 569 ms 131428 KB Output is correct
4 Correct 582 ms 134288 KB Output is correct
5 Correct 574 ms 132936 KB Output is correct
6 Correct 584 ms 132292 KB Output is correct
7 Correct 586 ms 131800 KB Output is correct
8 Correct 568 ms 136016 KB Output is correct
9 Correct 600 ms 132144 KB Output is correct
10 Correct 547 ms 132276 KB Output is correct
11 Correct 568 ms 133676 KB Output is correct
12 Correct 577 ms 131924 KB Output is correct
13 Correct 628 ms 135884 KB Output is correct
14 Correct 559 ms 132804 KB Output is correct
15 Correct 570 ms 132700 KB Output is correct
16 Correct 587 ms 133472 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 131448 KB Output is correct
2 Correct 590 ms 134024 KB Output is correct
3 Correct 582 ms 135016 KB Output is correct
4 Correct 563 ms 135416 KB Output is correct
5 Correct 569 ms 136388 KB Output is correct
6 Correct 557 ms 134852 KB Output is correct
7 Correct 559 ms 133444 KB Output is correct
8 Correct 569 ms 135432 KB Output is correct
9 Correct 569 ms 136008 KB Output is correct
10 Correct 590 ms 136740 KB Output is correct
11 Correct 553 ms 135484 KB Output is correct
12 Correct 556 ms 133932 KB Output is correct
13 Correct 569 ms 135032 KB Output is correct
14 Correct 553 ms 135816 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 5 ms 14940 KB Output is correct
3 Correct 4 ms 14940 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 5 ms 15056 KB Output is correct
6 Correct 3 ms 16216 KB Output is correct
7 Correct 4 ms 14940 KB Output is correct
8 Correct 3 ms 16220 KB Output is correct
9 Correct 3 ms 16220 KB Output is correct
10 Correct 4 ms 14940 KB Output is correct
11 Correct 3 ms 16336 KB Output is correct
12 Correct 4 ms 14940 KB Output is correct
13 Correct 3 ms 16220 KB Output is correct
14 Correct 4 ms 14980 KB Output is correct
15 Correct 4 ms 14940 KB Output is correct
16 Correct 3 ms 16220 KB Output is correct
17 Correct 3 ms 14940 KB Output is correct
18 Correct 4 ms 14940 KB Output is correct
19 Correct 4 ms 14940 KB Output is correct
20 Correct 4 ms 14940 KB Output is correct
21 Correct 3 ms 16220 KB Output is correct
22 Correct 4 ms 16216 KB Output is correct
23 Correct 4 ms 14940 KB Output is correct
24 Correct 4 ms 14940 KB Output is correct
25 Correct 3 ms 16220 KB Output is correct
26 Correct 3 ms 16220 KB Output is correct
27 Correct 4 ms 15008 KB Output is correct
28 Correct 4 ms 14936 KB Output is correct
29 Correct 4 ms 14940 KB Output is correct
30 Correct 3 ms 16344 KB Output is correct
31 Correct 5 ms 14940 KB Output is correct
32 Correct 3 ms 16220 KB Output is correct
33 Correct 592 ms 133704 KB Output is correct
34 Correct 534 ms 134480 KB Output is correct
35 Correct 581 ms 134748 KB Output is correct
36 Correct 555 ms 134716 KB Output is correct
37 Correct 584 ms 131820 KB Output is correct
38 Correct 563 ms 134440 KB Output is correct
39 Correct 578 ms 134832 KB Output is correct
40 Correct 589 ms 134444 KB Output is correct
41 Correct 565 ms 134488 KB Output is correct
42 Correct 561 ms 136912 KB Output is correct
43 Correct 546 ms 132188 KB Output is correct
44 Correct 586 ms 135568 KB Output is correct
45 Correct 569 ms 134500 KB Output is correct
46 Correct 618 ms 134472 KB Output is correct
47 Correct 582 ms 133200 KB Output is correct
48 Correct 576 ms 134112 KB Output is correct
49 Correct 569 ms 131428 KB Output is correct
50 Correct 582 ms 134288 KB Output is correct
51 Correct 574 ms 132936 KB Output is correct
52 Correct 584 ms 132292 KB Output is correct
53 Correct 586 ms 131800 KB Output is correct
54 Correct 568 ms 136016 KB Output is correct
55 Correct 600 ms 132144 KB Output is correct
56 Correct 547 ms 132276 KB Output is correct
57 Correct 568 ms 133676 KB Output is correct
58 Correct 577 ms 131924 KB Output is correct
59 Correct 628 ms 135884 KB Output is correct
60 Correct 559 ms 132804 KB Output is correct
61 Correct 570 ms 132700 KB Output is correct
62 Correct 587 ms 133472 KB Output is correct
63 Correct 598 ms 131448 KB Output is correct
64 Correct 590 ms 134024 KB Output is correct
65 Correct 582 ms 135016 KB Output is correct
66 Correct 563 ms 135416 KB Output is correct
67 Correct 569 ms 136388 KB Output is correct
68 Correct 557 ms 134852 KB Output is correct
69 Correct 559 ms 133444 KB Output is correct
70 Correct 569 ms 135432 KB Output is correct
71 Correct 569 ms 136008 KB Output is correct
72 Correct 590 ms 136740 KB Output is correct
73 Correct 553 ms 135484 KB Output is correct
74 Correct 556 ms 133932 KB Output is correct
75 Correct 569 ms 135032 KB Output is correct
76 Correct 553 ms 135816 KB Output is correct
77 Correct 587 ms 133744 KB Output is correct
78 Correct 592 ms 135200 KB Output is correct
79 Correct 611 ms 132736 KB Output is correct
80 Correct 586 ms 133000 KB Output is correct
81 Correct 592 ms 133448 KB Output is correct
82 Correct 597 ms 133724 KB Output is correct
83 Correct 608 ms 132948 KB Output is correct
84 Correct 590 ms 135236 KB Output is correct
85 Correct 601 ms 134820 KB Output is correct
86 Correct 612 ms 136276 KB Output is correct
87 Correct 569 ms 135760 KB Output is correct
88 Correct 552 ms 135776 KB Output is correct
89 Correct 563 ms 133532 KB Output is correct
90 Correct 576 ms 135184 KB Output is correct
91 Correct 534 ms 134244 KB Output is correct
92 Correct 570 ms 132980 KB Output is correct
93 Correct 542 ms 134612 KB Output is correct
94 Correct 552 ms 137420 KB Output is correct
95 Correct 568 ms 136352 KB Output is correct
96 Correct 542 ms 134204 KB Output is correct
97 Correct 544 ms 134356 KB Output is correct
98 Correct 593 ms 132384 KB Output is correct
99 Correct 604 ms 134080 KB Output is correct
100 Correct 625 ms 134372 KB Output is correct
101 Correct 619 ms 131920 KB Output is correct
102 Correct 611 ms 134092 KB Output is correct