oj.uz

Submission #555054

# Submission time Handle Problem Language Result Execution time Memory
555054 2022-04-30T05:20:47 Z kshitij_sodani Fish 2 (JOI22_fish2) C++14
8 / 100
 4000 ms 26364 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];
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--){
			int tt,l,r;
			cin>>tt>>l>>r;
			if(tt==1){
				l--;
				it[l]=r;
				
			}
			else{
				l--;
				r--;
				for(int 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<int> cur;
				for(int ii=l;ii<=r;ii++){
					cur.insert(ii);
				}
				vector<int> dd;
				for(int j=l;j<=r;j++){
					for(int 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(int j=l+1;j<=r;j++){
					if(it[j]>(pre[j]-pre[l])){
						cur.erase(l);
						break;
					}
				}
				for(int 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(int 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;
		}
	}
	while(q--){
		int tt,l,r;
		cin>>tt>>l>>r;
		if(tt==1){
			l--;
		}
		else{
			l--;
			r--;
			if(l==r){
				cout<<1<<endl;
				continue;
			}
			int ind=l;
			for(int i=l+1;i<=r;i++){
				if(it[i]-(pre[i]-pre[l])>0){
					ind=i;
				}
			}
			int ind2=r;
			for(int i=r-1;i>=l;i--){
				if(it[i]-(pre[r+1]-pre[i+1])>0){
					ind2=i;
				}
			}
			int su=0;
			for(int 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 7252 KB Output is correct
2 Correct 35 ms 17812 KB Output is correct
3 Correct 47 ms 19972 KB Output is correct
4 Correct 34 ms 18348 KB Output is correct
5 Correct 55 ms 19968 KB Output is correct
6 Correct 32 ms 15820 KB Output is correct
7 Correct 37 ms 17996 KB Output is correct
8 Correct 31 ms 15824 KB Output is correct
9 Correct 34 ms 18124 KB Output is correct
10 Correct 55 ms 25056 KB Output is correct
11 Correct 57 ms 26364 KB Output is correct
12 Correct 32 ms 16588 KB Output is correct
13 Correct 29 ms 16472 KB Output is correct
14 Correct 33 ms 17352 KB Output is correct
15 Correct 35 ms 17352 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 7252 KB Output is correct
2 Correct 35 ms 17812 KB Output is correct
3 Correct 47 ms 19972 KB Output is correct
4 Correct 34 ms 18348 KB Output is correct
5 Correct 55 ms 19968 KB Output is correct
6 Correct 32 ms 15820 KB Output is correct
7 Correct 37 ms 17996 KB Output is correct
8 Correct 31 ms 15824 KB Output is correct
9 Correct 34 ms 18124 KB Output is correct
10 Correct 55 ms 25056 KB Output is correct
11 Correct 57 ms 26364 KB Output is correct
12 Correct 32 ms 16588 KB Output is correct
13 Correct 29 ms 16472 KB Output is correct
14 Correct 33 ms 17352 KB Output is correct
15 Correct 35 ms 17352 KB Output is correct
16 Correct 5 ms 7380 KB Output is correct
17 Execution timed out 4067 ms 20948 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 7252 KB Output is correct
2 Correct 35 ms 17812 KB Output is correct
3 Correct 47 ms 19972 KB Output is correct
4 Correct 34 ms 18348 KB Output is correct
5 Correct 55 ms 19968 KB Output is correct
6 Correct 32 ms 15820 KB Output is correct
7 Correct 37 ms 17996 KB Output is correct
8 Correct 31 ms 15824 KB Output is correct
9 Correct 34 ms 18124 KB Output is correct
10 Correct 55 ms 25056 KB Output is correct
11 Correct 57 ms 26364 KB Output is correct
12 Correct 32 ms 16588 KB Output is correct
13 Correct 29 ms 16472 KB Output is correct
14 Correct 33 ms 17352 KB Output is correct
15 Correct 35 ms 17352 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 -