oj.uz

Submission #553786

# Submission time Handle Problem Language Result Execution time Memory
553786 2022-04-27T03:12:42 Z amunduzbaev Fish 2 (JOI22_fish2) C++17
8 / 100
 40 ms 19220 KB 
#include "bits/stdc++.h"
using namespace std;

#define int long long
#define ar array

const int N = 1e5 + 5;
const int inf = 1e9;
int a[N], is[N];
int st[N][20], pref[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	a[0] = a[n+1] = inf * N;
	for(int i=1;i<=n;i++){
		pref[i] = pref[i-1] + a[i];
		st[i][0] = pref[i-1] + a[i-1];
	}
	for(int j=1;j<20;j++){
		for(int i=1;i+(1 << (j-1)) <=n;i++){
			st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1]);
		}
	}
	
	auto get = [&](int l, int r){
		int lg = __lg(r - l + 1);
		return max(st[l][lg], st[r - (1 << lg) + 1][lg]);
	};
	
	int q; cin>>q;
	int t, l, r; cin>>t>>l>>r;
	
	for(int i=1;i<=n;i++){
		int l = 1 + (i == n), r = i + 1;
		while(l < r){
			int m = (l + r) >> 1;
			
			auto check = [&](int l){
				return pref[i] - a[i+1] < pref[l-1];
			};
			
			if(check(m)) r = m;
			else l = m + 1;
		}
		int pl = l;
		// cout<<pl<<" "<<r<<"\n";
		r = i + 1;
		while(l < r){
			auto check = [&](int pr){
				return pref[i] < get(pl, pr);
			};
			
			int m = (l + r) >> 1;
			if(check(m)) r = m;
			else l = m + 1;
		}
		
		is[l]++, is[i+1]--;
		// cout<<i<<" "<<l<<"\n";
	}
	
	for(int i=1;i<=n;i++) is[i] += is[i-1];
	int res=0;
	for(int i=1;i<=n;i++){
		res += !is[i];
	}
	
	cout<<res<<"\n";
	return 0;
}

/*

5
6 4 2 2 6
1
2 1 5 

*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 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 0 ms 340 KB Output is correct
2 Correct 33 ms 18252 KB Output is correct
3 Correct 33 ms 18632 KB Output is correct
4 Correct 35 ms 18764 KB Output is correct
5 Correct 34 ms 18640 KB Output is correct
6 Correct 38 ms 19204 KB Output is correct
7 Correct 32 ms 18380 KB Output is correct
8 Correct 40 ms 19220 KB Output is correct
9 Correct 34 ms 18504 KB Output is correct
10 Correct 35 ms 18880 KB Output is correct
11 Correct 38 ms 18500 KB Output is correct
12 Correct 33 ms 18544 KB Output is correct
13 Correct 36 ms 18564 KB Output is correct
14 Correct 35 ms 18792 KB Output is correct
15 Correct 36 ms 18888 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 33 ms 18252 KB Output is correct
3 Correct 33 ms 18632 KB Output is correct
4 Correct 35 ms 18764 KB Output is correct
5 Correct 34 ms 18640 KB Output is correct
6 Correct 38 ms 19204 KB Output is correct
7 Correct 32 ms 18380 KB Output is correct
8 Correct 40 ms 19220 KB Output is correct
9 Correct 34 ms 18504 KB Output is correct
10 Correct 35 ms 18880 KB Output is correct
11 Correct 38 ms 18500 KB Output is correct
12 Correct 33 ms 18544 KB Output is correct
13 Correct 36 ms 18564 KB Output is correct
14 Correct 35 ms 18792 KB Output is correct
15 Correct 36 ms 18888 KB Output is correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 33 ms 18252 KB Output is correct
3 Correct 33 ms 18632 KB Output is correct
4 Correct 35 ms 18764 KB Output is correct
5 Correct 34 ms 18640 KB Output is correct
6 Correct 38 ms 19204 KB Output is correct
7 Correct 32 ms 18380 KB Output is correct
8 Correct 40 ms 19220 KB Output is correct
9 Correct 34 ms 18504 KB Output is correct
10 Correct 35 ms 18880 KB Output is correct
11 Correct 38 ms 18500 KB Output is correct
12 Correct 33 ms 18544 KB Output is correct
13 Correct 36 ms 18564 KB Output is correct
14 Correct 35 ms 18792 KB Output is correct
15 Correct 36 ms 18888 KB Output is correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -