Submission #963889

#	Time	Username	Problem	Language	Result	Execution time	Memory
963889		vqpahmad	Financial Report (JOI21_financial)	C++14	0 / 100	4067 ms	17240 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e6 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int dp[MAXN];
const int off = (1<<20);
struct sgt {
#define ls (idx<<1)
#define rs (idx<<1|1)
	int t[off<<1];
	int unit = 0;
	void pull(int idx){
		t[idx] = max(t[ls], t[rs]);
	}
	void update(int idx, int u){
		t[idx+=off] = u;
		while (idx/=2)
			pull(idx);
	}
	int get(int l, int r, int idx=1, int lo=0, int hi=off){
		if (r <= lo || hi <= l) 
			return unit;
		if (l <= lo && hi <= r)
			return t[idx];
		int mi = (lo+hi)>>1;
		return max(get(l, r, ls, lo, mi), get(l, r, rs, mi, hi));
	}
} seg;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, d;
	cin >> n >> d;
	vector<int> a(n);
	vector<int> deco(n);
	for (int i = 0; i < n; i++){
		cin >> a[i];
		deco[i] = a[i];
	}
	sort(all(deco));
	for (int i = 0; i < n; i++){
		a[i] = lower_bound(all(deco), a[i]) - deco.begin() + 1;
	}
	deque<int> dq;
	priority_queue<int, vector<int>, greater<int>> pq;
	for (int i = 0; i < n; i++){
		// delete what you need to delete
		while (sz(dq) && a[dq.back()] >= a[i]) dq.pop_back();
		dq.push_back(i);
		if (i - dq.front() > d){
			dq.pop_front();
		}
		for (int j = 0; j < a[dq.front()]; j++){
			seg.update(j, 0);
		}
		dp[i] = seg.get(0, a[i]) + 1;
		seg.update(a[i], dp[i]);
	}
	cout << *max_element(dp, dp + n);
}

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