Submission #799916

#	Time	Username	Problem	Language	Result	Execution time	Memory
799916		fatemetmhr	Financial Report (JOI21_financial)	C++17	100 / 100	526 ms	42080 KiB

Main

// Be name khoda //

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second
#define mp     make_pair


const int maxn5 = 3e5 + 10;
const int maxnt = 2e6 + 10;



int n, d, a[maxn5], par[maxn5], lef[maxn5];
vector <int> req[maxn5];
vector <pair<int, int>> av;
bool mark[maxn5];
set <int> big;


namespace seg{
	int mx[maxnt];

	void upd(int l, int r, int id, int val, int v){
		if(r - l == 1){
			mx[v] = val;
			return;
		}
		int mid = (l + r) >> 1;
		if(id < mid)
			upd(l, mid, id, val, v * 2);
		else
			upd(mid, r, id, val, v * 2 + 1);
		mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
	}

	int get_max(int l, int r, int lq, int rq, int v){
		if(rq <= l || r <= lq)
			return 0;
		if(lq <= l && r <= rq)
			return mx[v];
		int mid = (l + r) >> 1;
		return max(get_max(l, mid, lq, rq, v * 2), get_max(mid, r, lq, rq, v * 2 + 1));
	}
}

int get_par(int a){return par[a] < 0 ? a : par[a] = get_par(par[a]);}

void merge(int x){
	int a = get_par(x), b = get_par(x - 1);
	if(a == b)
		return;
	if((-par[a]) < (-par[b]))
		swap(a, b);
	par[a] += par[b];
	par[b] = a;
	lef[a] = min(lef[a], lef[b]);
	if((-par[a]) >= d)
		big.insert(lef[a]);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> n >> d;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		av.pb({a[i], -i});
	}
	int ans = 0;
	sort(all(av));
	for(int i = 0; i < n; i++){
		lef[i] = i;
		a[i] = lower_bound(all(av), mp(a[i], -i)) - av.begin();
	}
	memset(par, -1, sizeof par);
	reverse(all(av));
	for(auto [val, id] : av){
		id *= -1;
		auto it = big.lower_bound(id);
		//cout << "ha? " << id << endl;
		if(it != big.end()){
			//cout << "ok " << id << ' ' << (*it) + d << endl;
			req[(*it) + d].pb(a[id]);
		}
		mark[id] = true;
		if(d == 1)
			big.insert(id);
		if(id && mark[id - 1])
			merge(id);
		if(id + 1 < n && mark[id + 1])
			merge(id + 1);
	}
	for(int i = 0; i < n; i++){
		for(auto id : req[i])
			seg::upd(0, n, id, 0, 1);
		int dp = seg::get_max(0, n, 0, a[i], 1) + 1;
		//cout << i << ' ' << a[i] << ' ' << dp << endl;
		seg::upd(0, n, a[i], dp, 1);
		if(a[i] >= a[n - 1])
			ans = max(ans, dp);
	}
	cout << ans << endl;
}

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