oj.uz

Submission #555059

# Submission time Handle Problem Language Result Execution time Memory
555059 2022-04-30T05:36:31 Z kshitij_sodani Fish 2 (JOI22_fish2) C++14
8 / 100
 4000 ms 30164 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 tree[4*100001][2];
void build(llo no,llo l,llo r){
	if(l==r){
		tree[no][0]=it[l]-pre[l];
		tree[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);
		tree[no][0]=max(tree[no*2+1][0],tree[no*2+2][0]);
		tree[no][1]=max(tree[no*2+1][1],tree[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 tree[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));
}
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;
/*	if(n<=500 and q<=500){
		while(q--){
			llo tt,l,r;
			cin>>tt>>l>>r;
			if(tt==1){
				l--;
				it[l]=r;
				
			}
			else{
				l--;
				r--;
				for(llo i=1;i<=n;i++){
					pre[i]=pre[i-1]+it[i-1];
				}
				if(l==r){
					cout<<1<<endl;
					continue;
				}
				if(it[l]>(pre[r+1]-pre[l+1])){
					cout<<1<<endl;
					continue;
				}
				if(it[r]>(pre[r]-pre[l])){
					cout<<1<<endl;
					continue;
				}
				set<llo> cur;
				for(llo ii=l;ii<=r;ii++){
					cur.insert(ii);
				}
				vector<llo> dd;
				for(llo j=l;j<=r;j++){
					for(llo k=j+2;k<=r;k++){
						if(pre[k]-pre[j+1]<it[j]){
							if(pre[k]-pre[j+1]<it[k]){
								//cout<<j<<":"<<k<<endl;
								auto jj=cur.lower_bound(j+1);
								while(jj!=cur.end()){
									if((*jj)<k){
										dd.pb((*jj));
										jj++;
									}
									else{
										break;
									}
								}
								for(auto jj:dd){
									cur.erase(jj);
								}
								dd.clear();
							}
						}
					}
				}
				for(llo j=l+1;j<=r;j++){
					if(it[j]>(pre[j]-pre[l])){
						cur.erase(l);
						break;
					}
				}
				for(llo j=r-1;j>=l;j--){
					if(it[j]>(pre[r+1]-pre[j+1])){
						cur.erase(r);
						break;
					}
				}
				cout<<cur.size()<<endl;

			}
		}
		return 0;
	}*/
	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==7){
			for(auto j:aa[i]){
				cout<<j<<",,";
			}
			cout<<endl;
		}*/
		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);
	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(int 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;
			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;
		}
	}









	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7380 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 4 ms 7380 KB Output is correct
2 Correct 44 ms 21836 KB Output is correct
3 Correct 49 ms 23712 KB Output is correct
4 Correct 40 ms 21900 KB Output is correct
5 Correct 52 ms 23648 KB Output is correct
6 Correct 30 ms 18992 KB Output is correct
7 Correct 38 ms 21864 KB Output is correct
8 Correct 31 ms 19020 KB Output is correct
9 Correct 48 ms 22104 KB Output is correct
10 Correct 55 ms 28636 KB Output is correct
11 Correct 67 ms 30164 KB Output is correct
12 Correct 42 ms 20408 KB Output is correct
13 Correct 41 ms 20328 KB Output is correct
14 Correct 36 ms 20912 KB Output is correct
15 Correct 36 ms 20868 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 44 ms 21836 KB Output is correct
3 Correct 49 ms 23712 KB Output is correct
4 Correct 40 ms 21900 KB Output is correct
5 Correct 52 ms 23648 KB Output is correct
6 Correct 30 ms 18992 KB Output is correct
7 Correct 38 ms 21864 KB Output is correct
8 Correct 31 ms 19020 KB Output is correct
9 Correct 48 ms 22104 KB Output is correct
10 Correct 55 ms 28636 KB Output is correct
11 Correct 67 ms 30164 KB Output is correct
12 Correct 42 ms 20408 KB Output is correct
13 Correct 41 ms 20328 KB Output is correct
14 Correct 36 ms 20912 KB Output is correct
15 Correct 36 ms 20868 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Execution timed out 4056 ms 24512 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 44 ms 21836 KB Output is correct
3 Correct 49 ms 23712 KB Output is correct
4 Correct 40 ms 21900 KB Output is correct
5 Correct 52 ms 23648 KB Output is correct
6 Correct 30 ms 18992 KB Output is correct
7 Correct 38 ms 21864 KB Output is correct
8 Correct 31 ms 19020 KB Output is correct
9 Correct 48 ms 22104 KB Output is correct
10 Correct 55 ms 28636 KB Output is correct
11 Correct 67 ms 30164 KB Output is correct
12 Correct 42 ms 20408 KB Output is correct
13 Correct 41 ms 20328 KB Output is correct
14 Correct 36 ms 20912 KB Output is correct
15 Correct 36 ms 20868 KB Output is correct
16 Incorrect 4 ms 7380 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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