oj.uz

Submission #555063

# Submission time Handle Problem Language Result Execution time Memory
555063 2022-04-30T05:55:37 Z kshitij_sodani Fish 2 (JOI22_fish2) C++14
8 / 100
 1675 ms 185208 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});
		}
	}		
	for(llo i=1;i<n;i++){
		if(pre[i]<it[i]){
			//ans--;
			break;
		}
	}

	for(llo i=n-2;i>=0;i--){
		if(it[i]>(pre[n]-pre[i+1])){
			//ans--;
			break;
		}
	}
	build(0,0,n-1);
	llo zz=0;
	while(q--){
		llo tt,l,r;
		cin>>tt>>l>>r;
		if(tt==1){
			l--;
		}
		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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 49620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 49664 KB Output is correct
2 Correct 766 ms 170752 KB Output is correct
3 Correct 765 ms 178564 KB Output is correct
4 Correct 729 ms 171020 KB Output is correct
5 Correct 587 ms 178352 KB Output is correct
6 Correct 283 ms 111360 KB Output is correct
7 Correct 785 ms 176428 KB Output is correct
8 Correct 289 ms 111492 KB Output is correct
9 Correct 760 ms 172556 KB Output is correct
10 Correct 568 ms 176976 KB Output is correct
11 Correct 632 ms 185208 KB Output is correct
12 Correct 682 ms 159120 KB Output is correct
13 Correct 746 ms 168772 KB Output is correct
14 Correct 442 ms 141888 KB Output is correct
15 Correct 430 ms 141720 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 49620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 49664 KB Output is correct
2 Correct 766 ms 170752 KB Output is correct
3 Correct 765 ms 178564 KB Output is correct
4 Correct 729 ms 171020 KB Output is correct
5 Correct 587 ms 178352 KB Output is correct
6 Correct 283 ms 111360 KB Output is correct
7 Correct 785 ms 176428 KB Output is correct
8 Correct 289 ms 111492 KB Output is correct
9 Correct 760 ms 172556 KB Output is correct
10 Correct 568 ms 176976 KB Output is correct
11 Correct 632 ms 185208 KB Output is correct
12 Correct 682 ms 159120 KB Output is correct
13 Correct 746 ms 168772 KB Output is correct
14 Correct 442 ms 141888 KB Output is correct
15 Correct 430 ms 141720 KB Output is correct
16 Correct 33 ms 49620 KB Output is correct
17 Incorrect 1675 ms 184000 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 49664 KB Output is correct
2 Correct 766 ms 170752 KB Output is correct
3 Correct 765 ms 178564 KB Output is correct
4 Correct 729 ms 171020 KB Output is correct
5 Correct 587 ms 178352 KB Output is correct
6 Correct 283 ms 111360 KB Output is correct
7 Correct 785 ms 176428 KB Output is correct
8 Correct 289 ms 111492 KB Output is correct
9 Correct 760 ms 172556 KB Output is correct
10 Correct 568 ms 176976 KB Output is correct
11 Correct 632 ms 185208 KB Output is correct
12 Correct 682 ms 159120 KB Output is correct
13 Correct 746 ms 168772 KB Output is correct
14 Correct 442 ms 141888 KB Output is correct
15 Correct 430 ms 141720 KB Output is correct
16 Incorrect 34 ms 49600 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 49620 KB Output isn't correct
2 Halted 0 ms 0 KB -