Submission #977241

#	Time	Username	Problem	Language	Result	Execution time	Memory
977241		Acanikolic	Financial Report (JOI21_financial)	C++14	5 / 100	187 ms	29228 KiB

Main

#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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35