oj.uz

Submission #555077

# Submission time Handle Problem Language Result Execution time Memory
555077 2022-04-30T06:16:54 Z kshitij_sodani Fish 2 (JOI22_fish2) C++14
36 / 100
 4000 ms 191640 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];
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});
		}
	}		
	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 49612 KB Output is correct
2 Correct 33 ms 49588 KB Output is correct
3 Correct 33 ms 49596 KB Output is correct
4 Correct 33 ms 49584 KB Output is correct
5 Correct 47 ms 49736 KB Output is correct
6 Correct 40 ms 50000 KB Output is correct
7 Correct 52 ms 49952 KB Output is correct
8 Correct 49 ms 49996 KB Output is correct
9 Correct 41 ms 50020 KB Output is correct
10 Correct 46 ms 49840 KB Output is correct
11 Correct 37 ms 49860 KB Output is correct
12 Correct 52 ms 49868 KB Output is correct
13 Correct 40 ms 49984 KB Output is correct
14 Correct 55 ms 49856 KB Output is correct
15 Correct 49 ms 50016 KB Output is correct
16 Correct 50 ms 50028 KB Output is correct
17 Correct 49 ms 50076 KB Output is correct
18 Correct 38 ms 50016 KB Output is correct
19 Correct 47 ms 49876 KB Output is correct
20 Correct 40 ms 49960 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 49620 KB Output is correct
2 Correct 810 ms 171536 KB Output is correct
3 Correct 790 ms 179436 KB Output is correct
4 Correct 747 ms 171560 KB Output is correct
5 Correct 613 ms 179352 KB Output is correct
6 Correct 299 ms 112212 KB Output is correct
7 Correct 881 ms 177064 KB Output is correct
8 Correct 326 ms 112208 KB Output is correct
9 Correct 832 ms 173296 KB Output is correct
10 Correct 620 ms 177672 KB Output is correct
11 Correct 625 ms 185984 KB Output is correct
12 Correct 681 ms 159892 KB Output is correct
13 Correct 733 ms 169616 KB Output is correct
14 Correct 444 ms 142548 KB Output is correct
15 Correct 429 ms 142492 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 49612 KB Output is correct
2 Correct 33 ms 49588 KB Output is correct
3 Correct 33 ms 49596 KB Output is correct
4 Correct 33 ms 49584 KB Output is correct
5 Correct 47 ms 49736 KB Output is correct
6 Correct 40 ms 50000 KB Output is correct
7 Correct 52 ms 49952 KB Output is correct
8 Correct 49 ms 49996 KB Output is correct
9 Correct 41 ms 50020 KB Output is correct
10 Correct 46 ms 49840 KB Output is correct
11 Correct 37 ms 49860 KB Output is correct
12 Correct 52 ms 49868 KB Output is correct
13 Correct 40 ms 49984 KB Output is correct
14 Correct 55 ms 49856 KB Output is correct
15 Correct 49 ms 50016 KB Output is correct
16 Correct 50 ms 50028 KB Output is correct
17 Correct 49 ms 50076 KB Output is correct
18 Correct 38 ms 50016 KB Output is correct
19 Correct 47 ms 49876 KB Output is correct
20 Correct 40 ms 49960 KB Output is correct
21 Correct 34 ms 49620 KB Output is correct
22 Correct 810 ms 171536 KB Output is correct
23 Correct 790 ms 179436 KB Output is correct
24 Correct 747 ms 171560 KB Output is correct
25 Correct 613 ms 179352 KB Output is correct
26 Correct 299 ms 112212 KB Output is correct
27 Correct 881 ms 177064 KB Output is correct
28 Correct 326 ms 112208 KB Output is correct
29 Correct 832 ms 173296 KB Output is correct
30 Correct 620 ms 177672 KB Output is correct
31 Correct 625 ms 185984 KB Output is correct
32 Correct 681 ms 159892 KB Output is correct
33 Correct 733 ms 169616 KB Output is correct
34 Correct 444 ms 142548 KB Output is correct
35 Correct 429 ms 142492 KB Output is correct
36 Execution timed out 4070 ms 65072 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 49620 KB Output is correct
2 Correct 810 ms 171536 KB Output is correct
3 Correct 790 ms 179436 KB Output is correct
4 Correct 747 ms 171560 KB Output is correct
5 Correct 613 ms 179352 KB Output is correct
6 Correct 299 ms 112212 KB Output is correct
7 Correct 881 ms 177064 KB Output is correct
8 Correct 326 ms 112208 KB Output is correct
9 Correct 832 ms 173296 KB Output is correct
10 Correct 620 ms 177672 KB Output is correct
11 Correct 625 ms 185984 KB Output is correct
12 Correct 681 ms 159892 KB Output is correct
13 Correct 733 ms 169616 KB Output is correct
14 Correct 444 ms 142548 KB Output is correct
15 Correct 429 ms 142492 KB Output is correct
16 Correct 34 ms 49572 KB Output is correct
17 Correct 1655 ms 184848 KB Output is correct
18 Correct 1679 ms 179880 KB Output is correct
19 Correct 1658 ms 185072 KB Output is correct
20 Correct 1686 ms 185268 KB Output is correct
21 Correct 1703 ms 185644 KB Output is correct
22 Correct 1716 ms 180064 KB Output is correct
23 Correct 1657 ms 185156 KB Output is correct
24 Correct 1727 ms 185632 KB Output is correct
25 Correct 1671 ms 185528 KB Output is correct
26 Correct 1731 ms 185500 KB Output is correct
27 Correct 1076 ms 118056 KB Output is correct
28 Correct 1054 ms 117888 KB Output is correct
29 Correct 1066 ms 118068 KB Output is correct
30 Correct 1510 ms 165476 KB Output is correct
31 Correct 1626 ms 181552 KB Output is correct
32 Correct 1699 ms 191640 KB Output is correct
33 Correct 1778 ms 183188 KB Output is correct
34 Correct 1606 ms 191148 KB Output is correct
35 Correct 1726 ms 190884 KB Output is correct
36 Correct 1648 ms 186060 KB Output is correct
37 Correct 1657 ms 178064 KB Output is correct
38 Correct 1471 ms 159124 KB Output is correct
39 Correct 1251 ms 148064 KB Output is correct
40 Correct 1362 ms 148692 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 49620 KB Output is correct
2 Correct 810 ms 171536 KB Output is correct
3 Correct 790 ms 179436 KB Output is correct
4 Correct 747 ms 171560 KB Output is correct
5 Correct 613 ms 179352 KB Output is correct
6 Correct 299 ms 112212 KB Output is correct
7 Correct 881 ms 177064 KB Output is correct
8 Correct 326 ms 112208 KB Output is correct
9 Correct 832 ms 173296 KB Output is correct
10 Correct 620 ms 177672 KB Output is correct
11 Correct 625 ms 185984 KB Output is correct
12 Correct 681 ms 159892 KB Output is correct
13 Correct 733 ms 169616 KB Output is correct
14 Correct 444 ms 142548 KB Output is correct
15 Correct 429 ms 142492 KB Output is correct
16 Correct 34 ms 49620 KB Output is correct
17 Execution timed out 4050 ms 64600 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 49612 KB Output is correct
2 Correct 33 ms 49588 KB Output is correct
3 Correct 33 ms 49596 KB Output is correct
4 Correct 33 ms 49584 KB Output is correct
5 Correct 47 ms 49736 KB Output is correct
6 Correct 40 ms 50000 KB Output is correct
7 Correct 52 ms 49952 KB Output is correct
8 Correct 49 ms 49996 KB Output is correct
9 Correct 41 ms 50020 KB Output is correct
10 Correct 46 ms 49840 KB Output is correct
11 Correct 37 ms 49860 KB Output is correct
12 Correct 52 ms 49868 KB Output is correct
13 Correct 40 ms 49984 KB Output is correct
14 Correct 55 ms 49856 KB Output is correct
15 Correct 49 ms 50016 KB Output is correct
16 Correct 50 ms 50028 KB Output is correct
17 Correct 49 ms 50076 KB Output is correct
18 Correct 38 ms 50016 KB Output is correct
19 Correct 47 ms 49876 KB Output is correct
20 Correct 40 ms 49960 KB Output is correct
21 Correct 34 ms 49620 KB Output is correct
22 Correct 810 ms 171536 KB Output is correct
23 Correct 790 ms 179436 KB Output is correct
24 Correct 747 ms 171560 KB Output is correct
25 Correct 613 ms 179352 KB Output is correct
26 Correct 299 ms 112212 KB Output is correct
27 Correct 881 ms 177064 KB Output is correct
28 Correct 326 ms 112208 KB Output is correct
29 Correct 832 ms 173296 KB Output is correct
30 Correct 620 ms 177672 KB Output is correct
31 Correct 625 ms 185984 KB Output is correct
32 Correct 681 ms 159892 KB Output is correct
33 Correct 733 ms 169616 KB Output is correct
34 Correct 444 ms 142548 KB Output is correct
35 Correct 429 ms 142492 KB Output is correct
36 Execution timed out 4070 ms 65072 KB Time limit exceeded
37 Halted 0 ms 0 KB -