Submission #1173308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173308		altern23	Financial Report (JOI21_financial)	C++20	48 / 100	4096 ms	26320 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const ll MAXN = 3e5;
const ll INF = 4e18;
const ll MOD = 998244353;

multiset<ll> st[MAXN + 5];

struct ST{
	ll n;
	vector<ll> sg;
	ST(ll _n){
		n = _n;
		sg = vector<ll> (4 * n + 5, -INF);
	}
	
	void upd(ll l, ll r, ll cur, ll idx){
		if(l == r){
			if(!st[idx].empty()) sg[cur] = *st[idx].rbegin();
			else sg[cur] = -INF;
		}
		else{
			ll mid = (l + r) / 2;
			if(idx <= mid) upd(l, mid, cur * 2, idx);
			else upd(mid + 1, r, cur * 2 + 1, idx);
			sg[cur] = max(sg[cur * 2], sg[cur * 2 + 1]);
		}
	}
	
	ll query(ll l, ll r, ll cur, ll x, ll y){
		if(l > y || r < x) return -INF;
		if(l >= x && r <= y) return sg[cur];
		ll mid = (l + r) / 2;
		return max(query(l, mid, cur * 2, x, y), query(mid + 1, r, cur * 2 + 1, x, y));
	}
};

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;
	// cin >> tc;
	for(;tc--;){
		ll N, D; cin >> N >> D;
		vector<ll> a(N + 5), comp;
		for(int i = 1; i <= N; i++){
			cin >> a[i];
			comp.push_back(a[i]);
		}
		
		sort(comp.begin(), comp.end());
		comp.erase(unique(comp.begin(), comp.end()), comp.end());
		
		ll M = comp.size();
		vector<ll> pos[N + 5];
		for(int i = 1; i <= N; i++){
			a[i] = lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin() + 1;
		}
		
		for(int i = 1; i <= N; i++){
			ll lst = i;
			for(int j = i + 1; j <= N; j++){
				if(j - lst > D){
					pos[j].push_back(i);
					break;
				}
				if(a[j] <= a[i]){
					lst = j;
				}
			}
		}
		
		ST sg(M);
		vector<ll> dp(N + 5);
		
		st[0].insert(0);
		sg.upd(0, M, 1, 0);

		for(int i = 1; i <= N; i++){
			for(auto x : pos[i]){
				st[a[x]].erase(st[a[x]].find(dp[x]));
				sg.upd(0, M, 1, a[x]);
			}
			
			dp[i] = sg.query(0, M, 1, 0, a[i] - 1) + 1;
			if(i == N){
				cout << max(dp[N], sg.query(0, M, 1, a[i], M)) << "\n";
			}
			st[a[i]].insert(dp[i]);
			sg.upd(0, M, 1, a[i]);
		}
	}   
}

/*

*/

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