oj.uz

Submission #906641

# Submission time Handle Problem Language Result Execution time Memory
906641 2024-01-14T15:46:59 Z dsyz Financial Report (JOI21_financial) C++17
0 / 100
 681 ms 73636 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 = 0, maximum2 = 0;
		if(!s.empty()){
			if(*s.begin() < arr[i]){
				maximum1 = max(maximum1,1 + root -> rmq(*s.begin(),arr[i] - 1));
			}
			maximum2 = max(maximum2,1 + 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 344 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 50376 KB Output is correct
2 Correct 119 ms 50628 KB Output is correct
3 Incorrect 158 ms 50632 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 72452 KB Output is correct
2 Correct 202 ms 72896 KB Output is correct
3 Correct 275 ms 71360 KB Output is correct
4 Correct 675 ms 73636 KB Output is correct
5 Correct 512 ms 70656 KB Output is correct
6 Correct 681 ms 72284 KB Output is correct
7 Incorrect 188 ms 72812 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -