oj.uz

Submission #975281

# Submission time Handle Problem Language Result Execution time Memory
975281 2024-05-04T16:55:10 Z LCJLY Financial Report (JOI21_financial) C++14
31 / 100
 2539 ms 70960 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[1]=max({a[1],a[3]+b[1]});
	temp[2]=max({b[2],b[3]+a[2]});
	temp[3]=a[3]+b[3];
	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,0,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+1;
		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 0 ms 504 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 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 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 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 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 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 0 ms 504 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 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 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 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 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Incorrect 1 ms 348 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 504 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 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 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 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 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Incorrect 1 ms 348 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1459 ms 70824 KB Output is correct
2 Correct 1296 ms 69128 KB Output is correct
3 Correct 2025 ms 69048 KB Output is correct
4 Correct 2364 ms 70876 KB Output is correct
5 Correct 1795 ms 70924 KB Output is correct
6 Correct 2354 ms 69556 KB Output is correct
7 Correct 971 ms 69676 KB Output is correct
8 Correct 1470 ms 69804 KB Output is correct
9 Correct 1000 ms 69304 KB Output is correct
10 Correct 1326 ms 70392 KB Output is correct
11 Correct 1438 ms 70704 KB Output is correct
12 Correct 1666 ms 69912 KB Output is correct
13 Correct 1719 ms 70416 KB Output is correct
14 Correct 2539 ms 70100 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1366 ms 70496 KB Output is correct
2 Correct 1824 ms 70584 KB Output is correct
3 Correct 2089 ms 69912 KB Output is correct
4 Correct 2119 ms 70960 KB Output is correct
5 Correct 1811 ms 70840 KB Output is correct
6 Correct 2060 ms 70604 KB Output is correct
7 Correct 1393 ms 69960 KB Output is correct
8 Correct 1348 ms 69560 KB Output is correct
9 Correct 1401 ms 69812 KB Output is correct
10 Correct 1728 ms 70572 KB Output is correct
11 Correct 2043 ms 68936 KB Output is correct
12 Correct 1816 ms 70788 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 504 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 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 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 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 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Incorrect 1 ms 348 KB Output isn't correct
29 Halted 0 ms 0 KB -