oj.uz

Submission #555088

# Submission time Handle Problem Language Result Execution time Memory
555088 2022-04-30T07:08:49 Z kshitij_sodani Fish 2 (JOI22_fish2) C++14
31 / 100
 4000 ms 191596 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);
}
llo cot[100001];
llo mi[100001];
llo vis[100001];
llo re[100001];
llo le[100001];
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(q<=1000){
		while(q--){
			int tt,l,r;
			cin>>tt>>l>>r;
			if(tt==1){
				l--;
				it[l]=r;
				for(llo i=0;i<n;i++){
					pre[i+1]=pre[i]+it[i];
				}
			}
			else{
				l--;
				r--;
				int ind=l-1;
				for(int i=l+1;i<=r;i++){
					if(it[i]>(pre[i]-pre[l])){
						ind=i-1;
					}
				}
				for(int i=l;i<=r+1;i++){
					vis[i]=0;
				}
/*				for(int j=l;j<=ind;j++){
					vis[j]=0;
				}*/
				vis[l]++;
				vis[ind+1]--;
				ind=r+1;
				for(int j=r-1;j>=l;j--){
					if(it[j]>(pre[r+1]-pre[j+1])){
						ind=j+1;
					}
				}
				vis[ind]++;
				vis[r+1]--;
				vector<pair<llo,llo>> ss;
				for(int i=0;i<n;i++){
					while(ss.size()){
						if(ss.back().a<=it[i]){
							ss.pop_back();
						}
						else{
							break;
						}
					}
					if(ss.size()){
						le[i]=ss.back().b;
					}
					else{
						le[i]=-1;
					}
					ss.pb({it[i],i});
				}
				ss.clear();
				for(int i=n-1;i>=0;i--){
					while(ss.size()){
						if(ss.back().a<=it[i]){
							ss.pop_back();
						}
						else{
							break;
						}
					}
					if(ss.size()){
						re[i]=ss.back().b;
					}
					else{
						re[i]=-1;
					}
					ss.pb({it[i],i});
				}
				ss.clear();
				for(int i=l+1;i<=r-1;i++){
					if(le[i]>=0 and re[i]>=0){
						if(it[le[i]]>pre[re[i]]-pre[le[i]+1]){
							if(it[re[i]]>pre[re[i]]-pre[le[i]+1]){
								vis[le[i]+1]++;
								vis[re[i]]--;
								//cout<<le[i]+1<<":"<<re[i]-1<<endl;
							}
						}
					}
				}
				llo su=0;
				llo su2=0;
				for(int j=l;j<=r;j++){
					su+=vis[j];
					if(su==0){
						su2++;
					}
				}
				cout<<su2<<endl;
			}
		}
		return 0;
	}

	for(llo i=0;i<n;i++){
		ne[i]={-1,-1};
	}
	llo ax=0;
	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});
					ax++;
					//cout<<i<<":"<<j<<endl;
				}
			}
		}

	}
	assert(ax<=2*n);
	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;
	llo qq=q;

	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){
				fin[zz]=1;
				if(n<=500 and qq<=500){
					cout<<1<<endl;
				}
				zz++;
				/*if(n<=500 and qq<=500){
					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}});
			}
			if(n<=500 and qq<=500){
				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(int i=0;i<n;i++){
		cot[i]=n;
	}
	for(llo i=n-1;i>=0;i--){
		for(auto j:ee[i]){
			llo xx=(j.a.b-j.a.a+1)-query2(0,0,n-1,j.a.a,j.a.b,j.b.a);
			/*for(int ii=j.a.a;ii<=j.a.b;ii++){
				if(cot[ii]<j.b.a){

				}
				else{
					xx++;
				}
			}*/
		//	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;
			cot[j.a]=j.b;
			update2(0,0,n-1,j.a,j.b);
		}
	}

		if(n<=500 and qq<=500){
			return 0;
		}
	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 Correct 32 ms 49620 KB Output is correct
2 Correct 33 ms 49592 KB Output is correct
3 Correct 32 ms 49608 KB Output is correct
4 Correct 33 ms 49552 KB Output is correct
5 Incorrect 34 ms 49592 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 49672 KB Output is correct
2 Correct 44 ms 53460 KB Output is correct
3 Correct 47 ms 53552 KB Output is correct
4 Correct 45 ms 53488 KB Output is correct
5 Correct 51 ms 53552 KB Output is correct
6 Correct 48 ms 53496 KB Output is correct
7 Correct 41 ms 53476 KB Output is correct
8 Correct 47 ms 53528 KB Output is correct
9 Correct 43 ms 53540 KB Output is correct
10 Correct 46 ms 53520 KB Output is correct
11 Correct 48 ms 53544 KB Output is correct
12 Correct 46 ms 53716 KB Output is correct
13 Correct 43 ms 53496 KB Output is correct
14 Correct 46 ms 53504 KB Output is correct
15 Correct 52 ms 53484 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 49620 KB Output is correct
2 Correct 33 ms 49592 KB Output is correct
3 Correct 32 ms 49608 KB Output is correct
4 Correct 33 ms 49552 KB Output is correct
5 Incorrect 34 ms 49592 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 49672 KB Output is correct
2 Correct 44 ms 53460 KB Output is correct
3 Correct 47 ms 53552 KB Output is correct
4 Correct 45 ms 53488 KB Output is correct
5 Correct 51 ms 53552 KB Output is correct
6 Correct 48 ms 53496 KB Output is correct
7 Correct 41 ms 53476 KB Output is correct
8 Correct 47 ms 53528 KB Output is correct
9 Correct 43 ms 53540 KB Output is correct
10 Correct 46 ms 53520 KB Output is correct
11 Correct 48 ms 53544 KB Output is correct
12 Correct 46 ms 53716 KB Output is correct
13 Correct 43 ms 53496 KB Output is correct
14 Correct 46 ms 53504 KB Output is correct
15 Correct 52 ms 53484 KB Output is correct
16 Correct 33 ms 49556 KB Output is correct
17 Correct 1724 ms 184724 KB Output is correct
18 Correct 1739 ms 179836 KB Output is correct
19 Correct 1669 ms 184876 KB Output is correct
20 Correct 1769 ms 185144 KB Output is correct
21 Correct 1715 ms 185476 KB Output is correct
22 Correct 1753 ms 179852 KB Output is correct
23 Correct 1730 ms 185044 KB Output is correct
24 Correct 1773 ms 185456 KB Output is correct
25 Correct 1717 ms 185392 KB Output is correct
26 Correct 1772 ms 185524 KB Output is correct
27 Correct 1107 ms 117928 KB Output is correct
28 Correct 1093 ms 117824 KB Output is correct
29 Correct 1098 ms 117912 KB Output is correct
30 Correct 1534 ms 165284 KB Output is correct
31 Correct 1622 ms 181336 KB Output is correct
32 Correct 1616 ms 191596 KB Output is correct
33 Correct 1742 ms 183292 KB Output is correct
34 Correct 1653 ms 191244 KB Output is correct
35 Correct 1720 ms 190860 KB Output is correct
36 Correct 1571 ms 185892 KB Output is correct
37 Correct 1683 ms 178044 KB Output is correct
38 Correct 1512 ms 159064 KB Output is correct
39 Correct 1296 ms 148380 KB Output is correct
40 Correct 1376 ms 148492 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 49672 KB Output is correct
2 Correct 44 ms 53460 KB Output is correct
3 Correct 47 ms 53552 KB Output is correct
4 Correct 45 ms 53488 KB Output is correct
5 Correct 51 ms 53552 KB Output is correct
6 Correct 48 ms 53496 KB Output is correct
7 Correct 41 ms 53476 KB Output is correct
8 Correct 47 ms 53528 KB Output is correct
9 Correct 43 ms 53540 KB Output is correct
10 Correct 46 ms 53520 KB Output is correct
11 Correct 48 ms 53544 KB Output is correct
12 Correct 46 ms 53716 KB Output is correct
13 Correct 43 ms 53496 KB Output is correct
14 Correct 46 ms 53504 KB Output is correct
15 Correct 52 ms 53484 KB Output is correct
16 Correct 34 ms 49612 KB Output is correct
17 Execution timed out 4056 ms 64364 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 49620 KB Output is correct
2 Correct 33 ms 49592 KB Output is correct
3 Correct 32 ms 49608 KB Output is correct
4 Correct 33 ms 49552 KB Output is correct
5 Incorrect 34 ms 49592 KB Output isn't correct
6 Halted 0 ms 0 KB -