oj.uz

Submission #555068

# Submission time Handle Problem Language Result Execution time Memory
555068 2022-04-30T06:02:26 Z kshitij_sodani Fish 2 (JOI22_fish2) C++14
13 / 100
 4000 ms 185288 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#define endl '\n'

llo it[100001];
vector<llo> aa[100001];
llo pre[100001];
vector<pair<llo,llo>> bb[100001];
vector<pair<llo,llo>> cc[100001];
pair<llo,llo> ne[100001];
llo fin[100001];
llo tree2[4*100001][2];
vector<pair<pair<llo,llo>,pair<llo,llo>>> ee[100001];
vector<pair<llo,llo>> ff[100001];
void build(llo no,llo l,llo r){
	if(l==r){
		tree2[no][0]=it[l]-pre[l];
		tree2[no][1]=it[l]+pre[l+1];
	}
	else{
		llo mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree2[no][0]=max(tree2[no*2+1][0],tree2[no*2+2][0]);
		tree2[no][1]=max(tree2[no*2+1][1],tree2[no*2+2][1]);
	}
}
llo query(llo no,llo l,llo r,llo aa,llo bb,llo ind){
	if(r<aa or l>bb or aa>bb){
		return -(llo)1e18;
	}
	if(aa<=l and r<=bb){
		return tree2[no][ind];
	}
	llo mid=(l+r)/2;
	return max(query(no*2+1,l,mid,aa,bb,ind),query(no*2+2,mid+1,r,aa,bb,ind));
}

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ord tree<pair<llo,llo>,null_type,less<pair<llo,llo>>,rb_tree_tag,tree_order_statistics_node_update>
ord tree3[4*100001];
void update2(llo no,llo l,llo r,llo i,llo j){
	tree3[no].insert({j,i});
	if(l<r){
		llo mid=(l+r)/2;
		if(i<=mid){
			update2(no*2+1,l,mid,i,j);
		}
		else{
			update2(no*2+2,mid+1,r,i,j);
		}
	}
}
llo query2(llo no,llo l,llo r,llo aa,llo bb,llo i){
	if(r<aa or l>bb or aa>bb){
		return 0;
	}
	if(aa<=l and r<=bb){
		if(tree3[no].size()==0){
			return 0;
		}

		//for(auto j:tree3[no]){
		//	cout<<j.a<<","<<j.b<<endl;
		//}
		return tree3[no].order_of_key({i,-1});
	}
	llo mid=(l+r)/2;
	return query2(no*2+1,l,mid,aa,bb,i)+query2(no*2+2,mid+1,r,aa,bb,i);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo n,q;
	cin>>n;
	for(llo i=0;i<n;i++){
		cin>>it[i];
		pre[i+1]=pre[i]+it[i];
	}
	cin>>q;

	for(llo i=0;i<n;i++){
		ne[i]={-1,-1};
	}
	for(llo i=1;i<n;i++){
		if(it[i]<it[i-1]){
			aa[i].pb(i);
		}
		for(auto j:aa[i-1]){
			if(pre[i+1]-pre[j]<it[j-1]){
				aa[i].pb(j);
			}
		}

		if(i<n-1){
			for(auto j:aa[i]){
				if(pre[i+1]-pre[j]<it[i+1]){
					bb[j-1].pb({i,j});
					cc[i+1].pb({i,j});
					//cout<<i<<":"<<j<<endl;

				}
			}
		}
	}
	multiset<pair<llo,llo>> cur;
	llo ans=n;
	for(llo i=0;i<n;i++){
		for(auto j:cc[i]){
			auto jj=cur.find({j.a,-j.b});
			cur.erase(jj);
		}
		if(cur.size()){
			pair<llo,llo> no=*(cur.begin());
			no.b=-no.b;
			ans--;
			ne[i]={no.b,no.a};
		}
		else{
		}
		for(auto j:bb[i]){
			cur.insert({j.a,-j.b});
		}
	}		
	build(0,0,n-1);
	llo zz=0;
	while(q--){
		llo tt,l,r;
		cin>>tt>>l>>r;
		if(tt==1){
			l--;
			it[l]=r;

			for(llo i=0;i<n;i++){
				ne[i]={-1,-1};
				aa[i].clear();
				bb[i].clear();
				cc[i].clear();
			}
			for(int i=0;i<n;i++){
				pre[i+1]=pre[i]+it[i];
			}
			for(llo i=1;i<n;i++){
				if(it[i]<it[i-1]){
					aa[i].pb(i);
				}
				for(auto j:aa[i-1]){
					if(pre[i+1]-pre[j]<it[j-1]){
						aa[i].pb(j);
					}
				}

				if(i<n-1){
					for(auto j:aa[i]){
						if(pre[i+1]-pre[j]<it[i+1]){
							bb[j-1].pb({i,j});
							cc[i+1].pb({i,j});
							//cout<<i<<":"<<j<<endl;

						}
					}
				}
			}
			multiset<pair<llo,llo>> cur;
			llo ans=n;
			for(llo i=0;i<n;i++){
				for(auto j:cc[i]){
					auto jj=cur.find({j.a,-j.b});
					cur.erase(jj);
				}
				if(cur.size()){
					pair<llo,llo> no=*(cur.begin());
					no.b=-no.b;
					ans--;
					ne[i]={no.b,no.a};
				}
				else{
				}
				for(auto j:bb[i]){
					cur.insert({j.a,-j.b});
				}
			}		
			build(0,0,n-1);
		}
		else{
			l--;
			r--;
			if(l==r){
				cout<<1<<endl;
				continue;
			}
			llo ind=r+1;
			for(llo j=19;j>=0;j--){
				if(ind-(1<<j)>l){
					if(query(0,0,n-1,ind-(1<<j),r,0)+pre[l]<=0){
						//cout<<query(0,0,n-1,ind-(1<<j),r,0)+pre[l]<<","<<ind-(1<<j)<<","<<r<<endl;
						ind-=(1<<j);
					}
				}
			}
			ind--;
			//cout<<ind<<":"<<endl;
		/*	llo ind=low-1;
			for(llo i=l+1;i<=r;i++){
				if(it[i]-(pre[i]-pre[l])>0){
					ind=i;
				}
			}*/
			llo ind2=l-1;
			for(llo j=19;j>=0;j--){
				if(ind2+(1<<j)<r){
					if(query(0,0,n-1,l,ind2+(1<<j),1)-pre[r+1]<=0){
						ind2+=(1<<j);
					}
				}
			}
			ind2++;
			/*for(llo i=r-1;i>=l;i--){
				if(it[i]-(pre[r+1]-pre[i+1])>0){
					ind2=i;
				}
			}
			ind2++;*/

			llo su=0;
			if(ind>ind2){
				fin[zz]=0;
			}
			else{
				ee[l].pb({{ind,ind2},{r,zz}});
			}
			for(llo j=ind;j<=ind2;j++){
				if(ne[j].a>=0){
					if(ne[j].a>l and ne[j].b<r){
						continue;
					}
				}
				su++;
			}
			cout<<su<<endl;
			zz++;
		}
	}

	for(llo i=0;i<n;i++){
		if(ne[i].a>=0){
			//cout<<i<<":"<<ne[i].a<<":"<<ne[i].b<<endl;
			ff[ne[i].a].pb({i,ne[i].b});
		}
	}
	for(llo i=n-1;i>=0;i--){
		for(auto j:ee[i]){
			llo xx=query2(0,0,n-1,j.a.a,j.a.b,j.b.a);
		//	cout<<i<<","<<j.a.a<<","<<j.a.b<<","<<j.b.a<<","<<j.b.b<<endl;
			//cout<<xx<<endl;
			xx=(j.a.b-j.a.a+1)-xx;
			fin[j.b.b]=xx;
		}
		for(auto j:ff[i]){
			//cout<<j.a<<"::"<<j.b<<endl;
			update2(0,0,n-1,j.a,j.b);
		}
	}

/*
	for(llo i=0;i<zz;i++){
		cout<<fin[i]<<endl;
	}*/








	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 49640 KB Output is correct
2 Correct 36 ms 49616 KB Output is correct
3 Correct 61 ms 49616 KB Output is correct
4 Correct 39 ms 49576 KB Output is correct
5 Correct 49 ms 49736 KB Output is correct
6 Correct 59 ms 50024 KB Output is correct
7 Correct 56 ms 49908 KB Output is correct
8 Correct 49 ms 50020 KB Output is correct
9 Correct 47 ms 49908 KB Output is correct
10 Correct 52 ms 49876 KB Output is correct
11 Correct 43 ms 49852 KB Output is correct
12 Correct 64 ms 49984 KB Output is correct
13 Correct 47 ms 50004 KB Output is correct
14 Correct 60 ms 49876 KB Output is correct
15 Correct 53 ms 50000 KB Output is correct
16 Correct 61 ms 50020 KB Output is correct
17 Correct 56 ms 49988 KB Output is correct
18 Correct 45 ms 50040 KB Output is correct
19 Correct 55 ms 49956 KB Output is correct
20 Correct 54 ms 49888 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 49572 KB Output is correct
2 Correct 888 ms 171016 KB Output is correct
3 Correct 825 ms 178848 KB Output is correct
4 Correct 788 ms 171084 KB Output is correct
5 Correct 608 ms 178712 KB Output is correct
6 Correct 318 ms 111628 KB Output is correct
7 Correct 852 ms 176448 KB Output is correct
8 Correct 302 ms 111616 KB Output is correct
9 Correct 809 ms 172856 KB Output is correct
10 Correct 605 ms 177092 KB Output is correct
11 Correct 644 ms 185288 KB Output is correct
12 Correct 713 ms 159268 KB Output is correct
13 Correct 758 ms 169112 KB Output is correct
14 Correct 448 ms 142108 KB Output is correct
15 Correct 446 ms 141996 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 49640 KB Output is correct
2 Correct 36 ms 49616 KB Output is correct
3 Correct 61 ms 49616 KB Output is correct
4 Correct 39 ms 49576 KB Output is correct
5 Correct 49 ms 49736 KB Output is correct
6 Correct 59 ms 50024 KB Output is correct
7 Correct 56 ms 49908 KB Output is correct
8 Correct 49 ms 50020 KB Output is correct
9 Correct 47 ms 49908 KB Output is correct
10 Correct 52 ms 49876 KB Output is correct
11 Correct 43 ms 49852 KB Output is correct
12 Correct 64 ms 49984 KB Output is correct
13 Correct 47 ms 50004 KB Output is correct
14 Correct 60 ms 49876 KB Output is correct
15 Correct 53 ms 50000 KB Output is correct
16 Correct 61 ms 50020 KB Output is correct
17 Correct 56 ms 49988 KB Output is correct
18 Correct 45 ms 50040 KB Output is correct
19 Correct 55 ms 49956 KB Output is correct
20 Correct 54 ms 49888 KB Output is correct
21 Correct 35 ms 49572 KB Output is correct
22 Correct 888 ms 171016 KB Output is correct
23 Correct 825 ms 178848 KB Output is correct
24 Correct 788 ms 171084 KB Output is correct
25 Correct 608 ms 178712 KB Output is correct
26 Correct 318 ms 111628 KB Output is correct
27 Correct 852 ms 176448 KB Output is correct
28 Correct 302 ms 111616 KB Output is correct
29 Correct 809 ms 172856 KB Output is correct
30 Correct 605 ms 177092 KB Output is correct
31 Correct 644 ms 185288 KB Output is correct
32 Correct 713 ms 159268 KB Output is correct
33 Correct 758 ms 169112 KB Output is correct
34 Correct 448 ms 142108 KB Output is correct
35 Correct 446 ms 141996 KB Output is correct
36 Execution timed out 4034 ms 65644 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 49572 KB Output is correct
2 Correct 888 ms 171016 KB Output is correct
3 Correct 825 ms 178848 KB Output is correct
4 Correct 788 ms 171084 KB Output is correct
5 Correct 608 ms 178712 KB Output is correct
6 Correct 318 ms 111628 KB Output is correct
7 Correct 852 ms 176448 KB Output is correct
8 Correct 302 ms 111616 KB Output is correct
9 Correct 809 ms 172856 KB Output is correct
10 Correct 605 ms 177092 KB Output is correct
11 Correct 644 ms 185288 KB Output is correct
12 Correct 713 ms 159268 KB Output is correct
13 Correct 758 ms 169112 KB Output is correct
14 Correct 448 ms 142108 KB Output is correct
15 Correct 446 ms 141996 KB Output is correct
16 Correct 36 ms 49644 KB Output is correct
17 Execution timed out 4078 ms 70300 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 49572 KB Output is correct
2 Correct 888 ms 171016 KB Output is correct
3 Correct 825 ms 178848 KB Output is correct
4 Correct 788 ms 171084 KB Output is correct
5 Correct 608 ms 178712 KB Output is correct
6 Correct 318 ms 111628 KB Output is correct
7 Correct 852 ms 176448 KB Output is correct
8 Correct 302 ms 111616 KB Output is correct
9 Correct 809 ms 172856 KB Output is correct
10 Correct 605 ms 177092 KB Output is correct
11 Correct 644 ms 185288 KB Output is correct
12 Correct 713 ms 159268 KB Output is correct
13 Correct 758 ms 169112 KB Output is correct
14 Correct 448 ms 142108 KB Output is correct
15 Correct 446 ms 141996 KB Output is correct
16 Correct 36 ms 49728 KB Output is correct
17 Execution timed out 4072 ms 64940 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 49640 KB Output is correct
2 Correct 36 ms 49616 KB Output is correct
3 Correct 61 ms 49616 KB Output is correct
4 Correct 39 ms 49576 KB Output is correct
5 Correct 49 ms 49736 KB Output is correct
6 Correct 59 ms 50024 KB Output is correct
7 Correct 56 ms 49908 KB Output is correct
8 Correct 49 ms 50020 KB Output is correct
9 Correct 47 ms 49908 KB Output is correct
10 Correct 52 ms 49876 KB Output is correct
11 Correct 43 ms 49852 KB Output is correct
12 Correct 64 ms 49984 KB Output is correct
13 Correct 47 ms 50004 KB Output is correct
14 Correct 60 ms 49876 KB Output is correct
15 Correct 53 ms 50000 KB Output is correct
16 Correct 61 ms 50020 KB Output is correct
17 Correct 56 ms 49988 KB Output is correct
18 Correct 45 ms 50040 KB Output is correct
19 Correct 55 ms 49956 KB Output is correct
20 Correct 54 ms 49888 KB Output is correct
21 Correct 35 ms 49572 KB Output is correct
22 Correct 888 ms 171016 KB Output is correct
23 Correct 825 ms 178848 KB Output is correct
24 Correct 788 ms 171084 KB Output is correct
25 Correct 608 ms 178712 KB Output is correct
26 Correct 318 ms 111628 KB Output is correct
27 Correct 852 ms 176448 KB Output is correct
28 Correct 302 ms 111616 KB Output is correct
29 Correct 809 ms 172856 KB Output is correct
30 Correct 605 ms 177092 KB Output is correct
31 Correct 644 ms 185288 KB Output is correct
32 Correct 713 ms 159268 KB Output is correct
33 Correct 758 ms 169112 KB Output is correct
34 Correct 448 ms 142108 KB Output is correct
35 Correct 446 ms 141996 KB Output is correct
36 Execution timed out 4034 ms 65644 KB Time limit exceeded
37 Halted 0 ms 0 KB -