oj.uz

Submission #906688

# Submission time Handle Problem Language Result Execution time Memory
906688 2024-01-14T17:54:21 Z dsyz Financial Report (JOI21_financial) C++17
5 / 100
 637 ms 70504 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
ll N,D;
ll arr[MAXN];
struct node {
	ll s,e,m,v;
	node *l, *r;
	node(ll _s,ll _e){
		s = _s;
		e = _e;
		m = (s + e) / 2;
		v = 0;
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void update(ll x,ll nval){
		if(s == e){
			v = nval;
			return;
		}else{
			if(x > m) r -> update(x,nval);
			else l -> update(x,nval);
			v = max(l -> v,r -> v);
		}
	}
	ll rmq(ll x,ll y){
		if(s == x && e == y){
			return v;
		}else{
			if(x > m) return r -> rmq(x,y);
			else if(y <= m) return l -> rmq(x,y);
			else return max(l -> rmq(x,m),r -> rmq(m + 1,y));
		}
	}
} *root;
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N>>D;
	root = new node(0,N + 5);
	vector<ll> d;
	for(ll i = 0;i < N;i++){
		cin>>arr[i];
		d.push_back(arr[i]);
	}
	sort(d.begin(),d.end());
	d.resize(unique(d.begin(),d.end()) - d.begin());
	for(ll i = 0;i < N;i++){
		arr[i] = lower_bound(d.begin(),d.end(),arr[i]) - d.begin();
	}
	multiset<ll> s;
	priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;
	ll dp[N];
	for(ll i = 0;i < N;i++){
		dp[i] = 1;
	}
	ll ans = 0;
	for(ll i = 0;i < N;i++){
		while(!pq.empty() && pq.top().first < i){
			s.erase(s.find(pq.top().second));
			pq.pop();
		}
		ll maximum1 = 1, maximum2 = 0;
		if(!s.empty()){
			if(*s.begin() < arr[i]){
				maximum1 = max(maximum1,1 + root -> rmq(*s.begin(),arr[i] - 1));
			}
			maximum2 = max(maximum2,root -> rmq(*s.begin(),N + 5));
		}
		dp[i] = max({dp[i],maximum1,maximum2});
		root -> update(arr[i],maximum1);
		ans = max(ans,dp[i]);
		pq.push({i + D,arr[i]});
		s.insert(arr[i]);
	}
	cout<<ans<<'\n';
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 47008 KB Output is correct
2 Correct 123 ms 47900 KB Output is correct
3 Incorrect 150 ms 49476 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 70504 KB Output is correct
2 Correct 200 ms 68368 KB Output is correct
3 Correct 289 ms 68536 KB Output is correct
4 Correct 637 ms 69404 KB Output is correct
5 Correct 494 ms 69432 KB Output is correct
6 Correct 620 ms 69956 KB Output is correct
7 Correct 180 ms 69064 KB Output is correct
8 Correct 199 ms 67940 KB Output is correct
9 Correct 190 ms 68540 KB Output is correct
10 Correct 304 ms 67776 KB Output is correct
11 Correct 624 ms 68972 KB Output is correct
12 Correct 538 ms 69628 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -