oj.uz

Submission #975299

# Submission time Handle Problem Language Result Execution time Memory
975299 2024-05-04T17:30:09 Z LCJLY Financial Report (JOI21_financial) C++14
19 / 100
 1787 ms 70072 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,long long>pii;
typedef array<int,5>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
 
int arr[300005];
int n,k;
 
inline pi2 combine(pi2 a, pi2 b){
	pi2 temp;
	temp[0]=max(a[0],b[0]);
	temp[3]=a[3]+b[3];
	temp[1]=a[1];
	if(a[1]==a[3]) temp[1]=a[3]+b[1];
	temp[2]=b[2];
	if(b[2]==b[3]) temp[2]=b[3]+a[2];
	temp[4]=max({a[4],b[4],a[2]+b[1]});
 	return temp;
}
 
struct node{
	int s,e,m;
	node *l,*r;
	pi2 v;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1){
		v={0,0,0,e-s+1,0};
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void upd(int x, int y){
		if(s==e){
			v[0]=y;
			v[1]=v[2]=v[3]=v[4]=1;
			return;
		}
		if(x<=m) l->upd(x,y);
		else r->upd(x,y);
		v=combine(l->v,r->v);
	}
	
	pi2 query(int x, int y){
		if(x<=s&&y>=e){
			return v;
		}
		if(y<=m) return l->query(x,y);
		if(x>m) return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
};
 
bool cmp(const pii a, const pii b){
	if(a.first==b.first){
		return a.second < b.second;
	}
	return a.first > b.first;
}
 
void solve(){
	cin >> n >> k;
	vector<pii>v;
	for(int x=1;x<=n;x++){
		cin >> arr[x];
		v.push_back({arr[x],x});
	}
	sort(v.begin(),v.end(),cmp);
	
	node st(0,n+5);
		
	int dp[n+5];
	memset(dp,0,sizeof(dp));
	int ans=0;
	for(int x=0;x<n;x++){
		int index=v[x].second;
		//show(index,index);
		int l=index;
		int r=n;
		int best=-1;
		int mid;
		while(l<=r){
			mid=(l+r)/2;
			pi2 hold=st.query(index,mid);
			if(hold[4]<=k){
				best=mid;
				l=mid+1;
			}
			else r=mid-1;
		}
		dp[index]=1;
		if(best!=-1){
			dp[index]=max(dp[index],st.query(index,best)[0]+1);
		}
		ans=max(ans,dp[index]);
		//show2(dp[index],dp[index],best,best);
		st.upd(index,dp[index]);
	}
	cout << ans;
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//freopen("in.txt","r",stdin);
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 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 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 464 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 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 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 464 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Incorrect 1 ms 348 KB Output isn't correct
28 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 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 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 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 464 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Incorrect 1 ms 348 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 922 ms 68788 KB Output is correct
2 Correct 1051 ms 69044 KB Output is correct
3 Incorrect 1787 ms 69712 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 951 ms 68856 KB Output is correct
2 Correct 1314 ms 68896 KB Output is correct
3 Correct 1646 ms 68300 KB Output is correct
4 Correct 1708 ms 70072 KB Output is correct
5 Correct 1368 ms 68856 KB Output is correct
6 Correct 1631 ms 68436 KB Output is correct
7 Correct 942 ms 69716 KB Output is correct
8 Correct 928 ms 69032 KB Output is correct
9 Correct 968 ms 68308 KB Output is correct
10 Correct 1335 ms 68160 KB Output is correct
11 Correct 1593 ms 68308 KB Output is correct
12 Correct 1297 ms 68612 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 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 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 464 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Incorrect 1 ms 348 KB Output isn't correct
28 Halted 0 ms 0 KB -