제출 #1192060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192060		Kel_Mahmut	Financial Report (JOI21_financial)	C++20	100 / 100	453 ms	24160 KiB

Main

#include<bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;

using namespace std;

struct SegmentTree{
	int n;
	vector<int> t;
	SegmentTree(int n) : n(n), t(4 * n){}
	void upd(int u, int tl, int tr, int pos, int val){
		if(tl == tr){
			t[u] = val;
			return;
		}
		int tm = (tl + tr) / 2;
		if(pos <= tm)
			upd(u * 2, tl, tm, pos, val);
		else
			upd(u * 2 + 1, tm + 1, tr, pos, val);
		t[u] = max(t[u * 2], t[u * 2 + 1]);
	}
	void upd(int pos, int val){
		upd(1, 0, n - 1, pos, val);
	}
	int query(int u, int tl, int tr, int ql, int qr){
		if(ql <= tl && tr <= qr)
			return t[u];
		int tm = (tl + tr) / 2;
		int ret = 0;
		if(ql <= tm) ret = max(ret, query(u * 2, tl, tm, ql, qr));
		if(tm < qr) ret = max(ret, query(u * 2 + 1, tm + 1, tr, ql, qr));
		return ret;
	}
	int query(int ql, int qr){
		return query(1, 0, n - 1, ql, qr);
	}
};

int main(){
	int n, d;
	cin >> n >> d;
	vector<int> a(n);
	for(int i = 0; i < n; i++) cin >> a[i];
	vector<array<int, 2>> s(n);
	for(int i = 0; i < n; i++) s[i][0] = a[i], s[i][1] = i;
	sort(all(s), [&](auto x, auto y){
		if(x[0] == y[0]) return x[1] > y[1];
		return x[0] < y[0];
	});
	vector<int> L(n);
	SegmentTree dp(n);
	for(int i = 0; i < n; i++) L[i] = i;
	function<int(int)> find = [&](int i){
		if(L[i] == i) return i;
		return L[i] = find(L[i]);
	};
	set<int> ind;
	for(int i = 0; i < n; i++){
		int cur = s[i][1];
		ind.insert(cur);
		auto it = ind.find(cur);
		if(it != ind.begin()){
			int sec = *prev(it);
			if(abs(cur - sec) <= d){
				sec = find(sec);
				int ata = find(cur);
				L[sec] = L[ata] = min(L[ata], L[sec]);
			}
		}
		if(next(it) != ind.end()){
			int sec = *next(it);
			if(abs(cur - sec) <= d){
				sec = find(sec);
				int ata = find(cur);
				L[sec] = L[ata] = min(L[ata], L[sec]);
			}
		}
		int l = find(cur);
		int val = dp.query(l, cur) + 1;
		dp.upd(cur, val);
	}
	cout << dp.query(0, n - 1) << 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