Submission #483742

#	Time	Username	Problem	Language	Result	Execution time	Memory
483742		minhcool	Financial Report (JOI21_financial)	C++17	100 / 100	455 ms	23876 KiB

Main

#include<bits/stdc++.h>

using namespace std; 

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define eb emplace_back
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5, MAXN = 1e7 + 5;
 
const long long oo = 1e9 + 7, mod = 1e9 + 7;

int n, d;
ii a[N];

int IT[N << 2], dp[N];

set<ii> se;// segments with length >= d

bool out[N];

void upd(int id, int l, int r, int pos, int vl){
	if(l == r){
		IT[id] = vl;
		return;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid) upd(id << 1, l, mid, pos, vl);
	else upd(id << 1 | 1, mid + 1, r, pos, vl);
	IT[id] = max(IT[id << 1], IT[id << 1 | 1]);
}

int get(int id, int l, int r, int L, int R){
	if(l > R || r < L || l > r) return 0;
	if(l >= L && r <= R) return IT[id];
	int mid = (l + r) >> 1;
	return max(get(id << 1, l, mid, L, R), get(id << 1 | 1, mid + 1, r, L, R));
}

bool cmp(ii a, ii b){
	if(a.fi != b.fi) return a.fi < b.fi;
	else return a.se > b.se;
}

void er(int temp){
	out[temp] =1 ;
	set<ii>::iterator it = se.lower_bound({temp, oo});
	if(it != se.begin()){
		//if(temp == 11) cout << temp << "\n";
		it--;
		ii tmp1 = (*it), tmp2 = {tmp1.fi, temp - 1}, tmp3 = {temp + 1, tmp1.se};
		if(tmp1.se < temp || tmp1.fi > temp) return;
		//if(temp == 11) cout << tmp1.fi << " " << tmp1.se << " " << temp << "\n";
		se.erase(tmp1);
		//cout << tmp2.fi << " " << tmp2.se << " " << tmp3.fi << " " << tmp3.se << "\n";
		if((tmp2.se - tmp2.fi + 1) >= d){
			//if(temp == 11) cout << tmp2.fi << " " << tmp2.se << "\n";
			se.insert(tmp2);
		}
		if((tmp3.se - tmp3.fi + 1) >= d) se.insert(tmp3);
	}
}

int saves[N];

void process(){
	cin >> n >> d;
	for(int i = 1; i <= n; i++){
		cin >> a[i].fi;
		a[i].se = i;
	}
	sort(a + 1, a + n + 1, cmp);
	se.insert({1, n});
	int ans = -1, itr = 1;
	for(int i = 1; i <= n; i++){
		//if(se.find({1, 11}) != se.end()) cout << i << "\n";
		int temp = a[i].se;
		//if(temp == 12) cout << out[11] << "\n";
		while(itr <= n && a[itr].fi == a[i].fi){
			er(a[itr].se);
			itr++;
		}
		//cout << i << " " << itr << "\n";
		//cout << i << "\n";
		//for(auto it : se) cout << it.fi << " " << it.se << "\n";
		int lst = 1;
		set<ii>::iterator it = se.lower_bound({temp, oo});
		if(it != se.begin()){
			it--;
			//if(temp == 12) cout << (*it).fi << " " << (*it).se << "\n";
			lst = (*it).se + 1;
		}
		saves[temp] = lst;
		//cout << i << " " << temp << " " << lst << "\n";
		dp[temp] = get(1, 1, n, lst, temp - 1) + 1;
		//cout << dp[temp] << "\n";
		upd(1, 1, n, temp, dp[temp]);
		ans = max(ans, dp[temp]);
	}
	//for(int i = 1; i <= n; i++) cout << i << " " << saves[i] << "\n";
	cout << ans;
}
 
signed main(){
	ios_base::sync_with_stdio(0);

	#ifdef nqm
		freopen("input.inp", "r", stdin);
		freopen("output.out", "w", stdout);
	#endif
	#ifndef nqm
		
	#endif

	process();
}

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