oj.uz

Submission #555056

# Submission time Handle Problem Language Result Execution time Memory
555056 2022-04-30T05:34:22 Z kshitij_sodani Fish 2 (JOI22_fish2) C++14
8 / 100
 4000 ms 30156 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=r;
			for(llo i=r-1;i>=l;i--){
				if(it[i]-(pre[r+1]-pre[i+1])>0){
					ind2=i;
				}
			}
			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 5 ms 7380 KB Output is correct
2 Correct 38 ms 21888 KB Output is correct
3 Correct 52 ms 23768 KB Output is correct
4 Correct 35 ms 21892 KB Output is correct
5 Correct 57 ms 23748 KB Output is correct
6 Correct 30 ms 19036 KB Output is correct
7 Correct 37 ms 21972 KB Output is correct
8 Correct 33 ms 19008 KB Output is correct
9 Correct 42 ms 22100 KB Output is correct
10 Correct 59 ms 28752 KB Output is correct
11 Correct 58 ms 30156 KB Output is correct
12 Correct 33 ms 20424 KB Output is correct
13 Correct 36 ms 20324 KB Output is correct
14 Correct 34 ms 20948 KB Output is correct
15 Correct 37 ms 20928 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 5 ms 7380 KB Output is correct
2 Correct 38 ms 21888 KB Output is correct
3 Correct 52 ms 23768 KB Output is correct
4 Correct 35 ms 21892 KB Output is correct
5 Correct 57 ms 23748 KB Output is correct
6 Correct 30 ms 19036 KB Output is correct
7 Correct 37 ms 21972 KB Output is correct
8 Correct 33 ms 19008 KB Output is correct
9 Correct 42 ms 22100 KB Output is correct
10 Correct 59 ms 28752 KB Output is correct
11 Correct 58 ms 30156 KB Output is correct
12 Correct 33 ms 20424 KB Output is correct
13 Correct 36 ms 20324 KB Output is correct
14 Correct 34 ms 20948 KB Output is correct
15 Correct 37 ms 20928 KB Output is correct
16 Correct 3 ms 7380 KB Output is correct
17 Execution timed out 4061 ms 24560 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 38 ms 21888 KB Output is correct
3 Correct 52 ms 23768 KB Output is correct
4 Correct 35 ms 21892 KB Output is correct
5 Correct 57 ms 23748 KB Output is correct
6 Correct 30 ms 19036 KB Output is correct
7 Correct 37 ms 21972 KB Output is correct
8 Correct 33 ms 19008 KB Output is correct
9 Correct 42 ms 22100 KB Output is correct
10 Correct 59 ms 28752 KB Output is correct
11 Correct 58 ms 30156 KB Output is correct
12 Correct 33 ms 20424 KB Output is correct
13 Correct 36 ms 20324 KB Output is correct
14 Correct 34 ms 20948 KB Output is correct
15 Correct 37 ms 20928 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 -