제출 #1243972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243972		nvujica	Financial Report (JOI21_financial)	C++20	100 / 100	348 ms	23148 KiB

Main

#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second

using namespace std;

const int maxn = 3e5 + 10, off = (1 << 19);

int n, d;
int a[maxn];
int dp[maxn];
vector <int> v;
set <int> s;
int par[maxn];
int rig[maxn];
vector <int> q;
int tour[2 * off];

bool cmp(int i, int j){
	return a[i] < a[j] || (a[i] == a[j] && i > j);
}

int find(int x){
	if(par[x] == x) return x;
	return par[x] = find(par[x]);
}

void update(int x, int val){
	x += off;
	tour[x] = max(tour[x], val);
	x /= 2;
	
	while(x){
		tour[x] = max(tour[x * 2], tour[x * 2 + 1]);
		x /= 2;
	}
}

int query(int x, int lo, int hi, int l, int r){
	if(hi <= lo) return 0;
	
	if(hi <= l || r <= lo) return 0;
	
	if(l <= lo && hi <= r) return tour[x];
	
	int mid = (lo + hi) / 2;
	return max(query(x * 2, lo, mid, l, r), query(x * 2 + 1, mid, hi, l, r));
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> d;
	
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		v.push_back(i);
	}
	
	s.insert(0);
	s.insert(n + 1);
	par[0] = 0;
	par[n + 1] = n + 1;
	
	sort(v.begin(), v.end(), cmp);
	
	for(auto x: v){
		auto it = s.lower_bound(x);
		
		par[x] = x;
		
		if(*it <= x + d) par[x] = *it;
		it--;
//		if(x == 6) cout << *it << endl;
		
		if(x <= *it + d) par[*it] = x;
		s.insert(x);
		
		rig[x] = min(n, find(x) + d);
	}
	
//	for(int i = 1; i <= n; i++) cout << rig[i] << ' ';
//	cout << endl;
	
	reverse(v.begin(), v.end());
	
	for(auto x: v){
		if(!q.empty() && a[x] != a[q.back()]){
			while(!q.empty()){
				int y = q.back();
				q.pop_back();
				update(y, dp[y]);
			}
		}
		
		dp[x] = query(1, 0, off, x + 1, rig[x] + 1) + 1;
		q.push_back(x);
//		cout << x << ' ' << dp[x] << endl;
	}
	
	int naj = 0;
	
	for(int i = 1; i <= n; i++){
		naj = max(naj, dp[i]);
	}
	
	cout << naj;
	
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35