oj.uz

답안 #975285

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
975285 2024-05-04T16:59:07 Z LCJLY Financial Report (JOI21_financial) C++14
45 / 100
 2462 ms 69820 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]});
	if(a[3]==0||b[3]==0) temp[3]=0;
	else 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 500 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 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 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 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 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 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 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 344 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 500 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 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 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 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 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 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 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 344 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 1 ms 472 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 1 ms 468 KB Output is correct
40 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 500 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 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 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 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 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 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 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 344 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 1 ms 472 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 1 ms 468 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 16 ms 1884 KB Output is correct
42 Incorrect 16 ms 1884 KB Output isn't correct
43 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1297 ms 69048 KB Output is correct
2 Correct 1176 ms 67704 KB Output is correct
3 Correct 1926 ms 68008 KB Output is correct
4 Correct 2355 ms 69524 KB Output is correct
5 Correct 1622 ms 69816 KB Output is correct
6 Correct 2333 ms 68460 KB Output is correct
7 Correct 926 ms 68168 KB Output is correct
8 Correct 1284 ms 68444 KB Output is correct
9 Correct 970 ms 68448 KB Output is correct
10 Correct 1279 ms 69148 KB Output is correct
11 Correct 1429 ms 69168 KB Output is correct
12 Correct 1681 ms 67940 KB Output is correct
13 Correct 1698 ms 68024 KB Output is correct
14 Correct 2462 ms 69820 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1269 ms 68532 KB Output is correct
2 Correct 1722 ms 68604 KB Output is correct
3 Correct 2013 ms 69660 KB Output is correct
4 Correct 1992 ms 69628 KB Output is correct
5 Correct 1865 ms 69560 KB Output is correct
6 Correct 2078 ms 69688 KB Output is correct
7 Correct 1285 ms 68412 KB Output is correct
8 Correct 1264 ms 68020 KB Output is correct
9 Correct 1330 ms 68808 KB Output is correct
10 Correct 1709 ms 68288 KB Output is correct
11 Correct 1973 ms 69520 KB Output is correct
12 Correct 1789 ms 69792 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 500 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 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 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 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 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 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 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 344 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 1 ms 472 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 1 ms 468 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 16 ms 1884 KB Output is correct
42 Incorrect 16 ms 1884 KB Output isn't correct
43 Halted 0 ms 0 KB -