oj.uz

답안 #975297

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
975297 2024-05-04T17:24:32 Z LCJLY Financial Report (JOI21_financial) C++14
19 / 100
 1760 ms 69584 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+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 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 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 0 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 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 0 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 1 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 344 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 14.0

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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 956 ms 68536 KB Output is correct
2 Correct 1026 ms 67768 KB Output is correct
3 Incorrect 1760 ms 68784 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 895 ms 68684 KB Output is correct
2 Correct 1321 ms 68324 KB Output is correct
3 Correct 1543 ms 68780 KB Output is correct
4 Correct 1556 ms 68528 KB Output is correct
5 Correct 1355 ms 69120 KB Output is correct
6 Correct 1636 ms 68408 KB Output is correct
7 Correct 947 ms 68760 KB Output is correct
8 Correct 902 ms 68688 KB Output is correct
9 Correct 962 ms 68536 KB Output is correct
10 Correct 1278 ms 69076 KB Output is correct
11 Correct 1579 ms 69584 KB Output is correct
12 Correct 1337 ms 69560 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 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 0 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 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 0 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 1 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 344 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Incorrect 1 ms 348 KB Output isn't correct
28 Halted 0 ms 0 KB -