oj.uz

답안 #977241

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
977241 2024-05-07T14:45:16 Z Acanikolic Financial Report (JOI21_financial) C++14
5 / 100
 187 ms 29228 KB 
#include <bits/stdc++.h>

#define int long long 

#define pb push_back

#define F first

#define S second

using namespace std;

const int N = 3e5 + 10;

int a[N],dp[N],st[N * 4];

void modify(int node,int tl,int tr,int index,int val) {
	if(tl > index || tr < index) return;
	if(tl == tr) {
		st[node] = max(st[node],val);
		return;
	}
	int mid = (tl + tr) / 2;
	modify(node * 2,tl,mid,index,val);
	modify(node * 2 + 1,mid + 1,tr,index,val);
	st[node] = max(st[node * 2],st[node * 2 + 1]);
}

int get(int node,int tl,int tr,int l,int r) {
	if(l > r) return 0;
	if(tl > r || tr < l) return 0;
	if(tl >= l && tr <= r) return st[node];
	int mid = (tl + tr) / 2;
	return max(get(node * 2,tl,mid,l,r),get(node * 2 + 1,mid + 1,tr,l,r));
}

bool cmp(pair<int,int>A,pair<int,int>B) {
	if(A.F == B.F) return A.S < B.S;
	return A.F < B.F;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n,d;
	cin >> n >> d;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		dp[i] = 1;
	}
	vector<pair<int,int>>vec;
	for(int i = 1; i <= n; i++) vec.pb({a[i],i});
	sort(vec.begin(),vec.end(),cmp);
	vector<pair<int,int>>updates; // update pos dpval
	for(int i = 0; i < n; i++) {
		if(i > 0 && vec[i].F != vec[i - 1].F) {
			for(auto X : updates) modify(1,1,n,X.F,X.S);
			updates.clear();
		}
 		int j = max(1ll,vec[i].S - d);
		updates.pb({vec[i].S,get(1,1,n,j,vec[i].S - 1) + 1});
	}
	for(auto X : updates) modify(1,1,n,X.F,X.S);
	cout << get(1,1,n,1,n);
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 3 ms 4440 KB Output is correct
11 Correct 2 ms 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4556 KB Output is correct
14 Correct 2 ms 4444 KB Output is correct
15 Incorrect 1 ms 4444 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 3 ms 4440 KB Output is correct
11 Correct 2 ms 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4556 KB Output is correct
14 Correct 2 ms 4444 KB Output is correct
15 Incorrect 1 ms 4444 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 3 ms 4440 KB Output is correct
11 Correct 2 ms 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4556 KB Output is correct
14 Correct 2 ms 4444 KB Output is correct
15 Incorrect 1 ms 4444 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 29008 KB Output is correct
2 Incorrect 160 ms 24612 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 29228 KB Output is correct
2 Correct 159 ms 22452 KB Output is correct
3 Correct 181 ms 22712 KB Output is correct
4 Correct 168 ms 23388 KB Output is correct
5 Correct 158 ms 22456 KB Output is correct
6 Correct 181 ms 23268 KB Output is correct
7 Correct 119 ms 23480 KB Output is correct
8 Correct 116 ms 22260 KB Output is correct
9 Correct 127 ms 24008 KB Output is correct
10 Correct 167 ms 23224 KB Output is correct
11 Correct 164 ms 23300 KB Output is correct
12 Correct 187 ms 23524 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 3 ms 4440 KB Output is correct
11 Correct 2 ms 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4556 KB Output is correct
14 Correct 2 ms 4444 KB Output is correct
15 Incorrect 1 ms 4444 KB Output isn't correct
16 Halted 0 ms 0 KB -