제출 #1149866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149866		Issa	Financial Report (JOI21_financial)	C++20	100 / 100	240 ms	24392 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 1e6 + 100;
const ll INF = (ll)1e18 + 100;
const int inf = 1e7 + 100;
const ll MOD = 1e9 + 7;
const int maxl = 16;
const ll P = 31;

int n, D;
int a[maxn];
int dp[maxn];
set<int> st;
int l[maxn];
int r[maxn];
int d[maxn * 4];

void upd(int i, int v = 1, int tl = 1, int tr = n){
	d[v] = max(d[v], dp[i]);
	if(tl < tr){
		int mid = (tl + tr) >> 1;
		if(i <= mid) upd(i, v<<1, tl, mid);
		else upd(i, v<<1|1, mid+1, tr);
	}
} int get(int l, int r, int v = 1, int tl = 1, int tr = n){
	if(tl > r || tr < l) return -inf;
	if(l <= tl && tr <= r) return d[v];
	int mid = (tl + tr) >> 1;
	return max(get(l, r, v<<1, tl, mid)
	, get(l, r, v<<1|1, mid+1, tr));
}

void del(int i){
	upd(i);
	if(r[i] - l[i] > D) st.insert(l[i]);
	r[l[i]] = r[i]; l[r[i]] = l[i];
}

void test(){
	cin >> n >> D;
	vector<int> v;
	for(int i = 1; i <= n; i++){
		l[i] = i-1;
		r[i] = i+1;
		cin >> a[i];
		v.push_back(i);
	} sort(v.begin(), v.end(), [](int i, int j){
		if(a[i] == a[j]) return i < j;
		return a[i] > a[j];
	});
	for(int i: v){
		auto it = st.lower_bound(i);
		int r; if(it == st.end()) r = n;
		else r = min(n, *it + D);
		dp[i] = get(i, r);
		if(r == n) dp[i] = max(dp[i], 0);
		dp[i]++; del(i);
	} cout << d[1];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    srand(time(0));
    int t = 1;
    while(t--) test();
}

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