oj.uz

Submission #555080

# Submission time Handle Problem Language Result Execution time Memory
555080 2022-04-30T06:43:59 Z kshitij_sodani Fish 2 (JOI22_fish2) C++14
36 / 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];
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<=10000){
		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--;
				for(int i=r;i>=l;i--){
					mi[i]=it[i]-pre[i];
					if(i<r){
						mi[i]=max(mi[i],mi[i+1]);
					}
					vis[i]=1;
				}
				int ind=l-1;
				for(int i=l+1;i<=r;i++){
					if(it[i]>(pre[i]-pre[l])){
						ind=i-1;
					}
				}
				for(int j=l;j<=ind;j++){
					vis[j]=0;
				}
				ind=r+1;
				for(int j=r-1;j>=l;j--){
					if(it[j]>(pre[r+1]-pre[j+1])){
						ind=j+1;
					}
				}
				for(int j=ind;j<=r;j++){
					vis[j]=0;
				}
				llo cur=l;
				while(cur<r-1){
					llo cur2=cur+2;
					//cout<<cur<<",";
					while(cur2<=r){
						if(it[cur]<=(pre[cur2]-pre[cur+1])){
							break;
						}
						if(cur==1){
							cout<<cur2<<",,"<<endl;
							cout<<mi[cur2]+pre[cur+1]<<":"<<endl;
						}
						if(mi[cur2]+pre[cur+1]>0){
							cur2++;
						}
						else{
							break;
						}
					}
					if(cur2==cur+2){
						cur++;
						continue;
					}
					else{
						for(int j=cur+1;j<=cur2-2;j++){
							vis[j]=0;
						}
						cur=cur2-1;
					}
				}
				//cout<<endl;

				llo su=0;
				for(int j=l;j<=r;j++){
					su+=vis[j];
				}
				cout<<su<<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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 49656 KB Output is correct
2 Correct 33 ms 49612 KB Output is correct
3 Correct 33 ms 49672 KB Output is correct
4 Correct 32 ms 49560 KB Output is correct
5 Correct 48 ms 49736 KB Output is correct
6 Correct 42 ms 50092 KB Output is correct
7 Correct 54 ms 49960 KB Output is correct
8 Correct 45 ms 50064 KB Output is correct
9 Correct 41 ms 49920 KB Output is correct
10 Correct 44 ms 49852 KB Output is correct
11 Correct 41 ms 49860 KB Output is correct
12 Correct 50 ms 49876 KB Output is correct
13 Correct 42 ms 50024 KB Output is correct
14 Correct 57 ms 49900 KB Output is correct
15 Correct 48 ms 50040 KB Output is correct
16 Correct 40 ms 49916 KB Output is correct
17 Correct 48 ms 49948 KB Output is correct
18 Correct 40 ms 50048 KB Output is correct
19 Correct 45 ms 49836 KB Output is correct
20 Correct 40 ms 49972 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 49612 KB Output is correct
2 Correct 783 ms 171512 KB Output is correct
3 Correct 772 ms 179472 KB Output is correct
4 Correct 722 ms 171856 KB Output is correct
5 Correct 574 ms 179316 KB Output is correct
6 Correct 289 ms 112200 KB Output is correct
7 Correct 792 ms 177044 KB Output is correct
8 Correct 285 ms 112268 KB Output is correct
9 Correct 747 ms 173328 KB Output is correct
10 Correct 571 ms 177616 KB Output is correct
11 Correct 604 ms 185884 KB Output is correct
12 Correct 677 ms 159880 KB Output is correct
13 Correct 739 ms 169540 KB Output is correct
14 Correct 441 ms 142520 KB Output is correct
15 Correct 429 ms 142488 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 49656 KB Output is correct
2 Correct 33 ms 49612 KB Output is correct
3 Correct 33 ms 49672 KB Output is correct
4 Correct 32 ms 49560 KB Output is correct
5 Correct 48 ms 49736 KB Output is correct
6 Correct 42 ms 50092 KB Output is correct
7 Correct 54 ms 49960 KB Output is correct
8 Correct 45 ms 50064 KB Output is correct
9 Correct 41 ms 49920 KB Output is correct
10 Correct 44 ms 49852 KB Output is correct
11 Correct 41 ms 49860 KB Output is correct
12 Correct 50 ms 49876 KB Output is correct
13 Correct 42 ms 50024 KB Output is correct
14 Correct 57 ms 49900 KB Output is correct
15 Correct 48 ms 50040 KB Output is correct
16 Correct 40 ms 49916 KB Output is correct
17 Correct 48 ms 49948 KB Output is correct
18 Correct 40 ms 50048 KB Output is correct
19 Correct 45 ms 49836 KB Output is correct
20 Correct 40 ms 49972 KB Output is correct
21 Correct 33 ms 49612 KB Output is correct
22 Correct 783 ms 171512 KB Output is correct
23 Correct 772 ms 179472 KB Output is correct
24 Correct 722 ms 171856 KB Output is correct
25 Correct 574 ms 179316 KB Output is correct
26 Correct 289 ms 112200 KB Output is correct
27 Correct 792 ms 177044 KB Output is correct
28 Correct 285 ms 112268 KB Output is correct
29 Correct 747 ms 173328 KB Output is correct
30 Correct 571 ms 177616 KB Output is correct
31 Correct 604 ms 185884 KB Output is correct
32 Correct 677 ms 159880 KB Output is correct
33 Correct 739 ms 169540 KB Output is correct
34 Correct 441 ms 142520 KB Output is correct
35 Correct 429 ms 142488 KB Output is correct
36 Execution timed out 4058 ms 64864 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 49612 KB Output is correct
2 Correct 783 ms 171512 KB Output is correct
3 Correct 772 ms 179472 KB Output is correct
4 Correct 722 ms 171856 KB Output is correct
5 Correct 574 ms 179316 KB Output is correct
6 Correct 289 ms 112200 KB Output is correct
7 Correct 792 ms 177044 KB Output is correct
8 Correct 285 ms 112268 KB Output is correct
9 Correct 747 ms 173328 KB Output is correct
10 Correct 571 ms 177616 KB Output is correct
11 Correct 604 ms 185884 KB Output is correct
12 Correct 677 ms 159880 KB Output is correct
13 Correct 739 ms 169540 KB Output is correct
14 Correct 441 ms 142520 KB Output is correct
15 Correct 429 ms 142488 KB Output is correct
16 Correct 33 ms 49612 KB Output is correct
17 Correct 1658 ms 184860 KB Output is correct
18 Correct 1668 ms 179864 KB Output is correct
19 Correct 1684 ms 184808 KB Output is correct
20 Correct 1720 ms 185420 KB Output is correct
21 Correct 1715 ms 185368 KB Output is correct
22 Correct 1733 ms 180012 KB Output is correct
23 Correct 1680 ms 185048 KB Output is correct
24 Correct 1718 ms 185524 KB Output is correct
25 Correct 1664 ms 185472 KB Output is correct
26 Correct 1761 ms 185416 KB Output is correct
27 Correct 1276 ms 117840 KB Output is correct
28 Correct 1209 ms 117768 KB Output is correct
29 Correct 1236 ms 117960 KB Output is correct
30 Correct 1771 ms 165280 KB Output is correct
31 Correct 1815 ms 181464 KB Output is correct
32 Correct 1828 ms 191596 KB Output is correct
33 Correct 1990 ms 183248 KB Output is correct
34 Correct 1796 ms 190996 KB Output is correct
35 Correct 1738 ms 190988 KB Output is correct
36 Correct 1579 ms 185944 KB Output is correct
37 Correct 1739 ms 177964 KB Output is correct
38 Correct 1471 ms 159128 KB Output is correct
39 Correct 1319 ms 148208 KB Output is correct
40 Correct 1391 ms 148504 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 49612 KB Output is correct
2 Correct 783 ms 171512 KB Output is correct
3 Correct 772 ms 179472 KB Output is correct
4 Correct 722 ms 171856 KB Output is correct
5 Correct 574 ms 179316 KB Output is correct
6 Correct 289 ms 112200 KB Output is correct
7 Correct 792 ms 177044 KB Output is correct
8 Correct 285 ms 112268 KB Output is correct
9 Correct 747 ms 173328 KB Output is correct
10 Correct 571 ms 177616 KB Output is correct
11 Correct 604 ms 185884 KB Output is correct
12 Correct 677 ms 159880 KB Output is correct
13 Correct 739 ms 169540 KB Output is correct
14 Correct 441 ms 142520 KB Output is correct
15 Correct 429 ms 142488 KB Output is correct
16 Correct 34 ms 49620 KB Output is correct
17 Execution timed out 4067 ms 64236 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 49656 KB Output is correct
2 Correct 33 ms 49612 KB Output is correct
3 Correct 33 ms 49672 KB Output is correct
4 Correct 32 ms 49560 KB Output is correct
5 Correct 48 ms 49736 KB Output is correct
6 Correct 42 ms 50092 KB Output is correct
7 Correct 54 ms 49960 KB Output is correct
8 Correct 45 ms 50064 KB Output is correct
9 Correct 41 ms 49920 KB Output is correct
10 Correct 44 ms 49852 KB Output is correct
11 Correct 41 ms 49860 KB Output is correct
12 Correct 50 ms 49876 KB Output is correct
13 Correct 42 ms 50024 KB Output is correct
14 Correct 57 ms 49900 KB Output is correct
15 Correct 48 ms 50040 KB Output is correct
16 Correct 40 ms 49916 KB Output is correct
17 Correct 48 ms 49948 KB Output is correct
18 Correct 40 ms 50048 KB Output is correct
19 Correct 45 ms 49836 KB Output is correct
20 Correct 40 ms 49972 KB Output is correct
21 Correct 33 ms 49612 KB Output is correct
22 Correct 783 ms 171512 KB Output is correct
23 Correct 772 ms 179472 KB Output is correct
24 Correct 722 ms 171856 KB Output is correct
25 Correct 574 ms 179316 KB Output is correct
26 Correct 289 ms 112200 KB Output is correct
27 Correct 792 ms 177044 KB Output is correct
28 Correct 285 ms 112268 KB Output is correct
29 Correct 747 ms 173328 KB Output is correct
30 Correct 571 ms 177616 KB Output is correct
31 Correct 604 ms 185884 KB Output is correct
32 Correct 677 ms 159880 KB Output is correct
33 Correct 739 ms 169540 KB Output is correct
34 Correct 441 ms 142520 KB Output is correct
35 Correct 429 ms 142488 KB Output is correct
36 Execution timed out 4058 ms 64864 KB Time limit exceeded
37 Halted 0 ms 0 KB -