Submission #963898

#	Time	Username	Problem	Language	Result	Execution time	Memory
963898		vqpahmad	Financial Report (JOI21_financial)	C++14	100 / 100	203 ms	11872 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));
	deco.erase(unique(all(deco)), deco.end());
	for (int i = 0; i < n; i++){
		a[i] = lower_bound(all(deco), a[i]) - deco.begin() + 1;
	}
	debug(a);
	deque<int> dq;
	priority_queue<int, vector<int>, greater<int>> pq;
	for (int i = 0; i < n; i++){
		// delete what you need to delete
		if (sz(dq)){
			if (i - dq.front() > d){
				dq.pop_front();
			}
			while (pq.top() < a[dq.front()]){
				seg.update(pq.top(), 0);
				pq.pop();
			}
		}
		dp[i] = seg.get(0, a[i]) + 1;
		debug(i, dp[i], a[i]);
		if (dp[i] > seg.t[a[i] + off]) seg.update(a[i], dp[i]);

		while (sz(dq) && a[dq.back()] >= a[i]) dq.pop_back();
		dq.push_back(i);
		pq.push(a[i]);
	}
	cout << *max_element(dp, dp + n);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42
      |                    ^~
Main.cpp:62:2: note: in expansion of macro 'debug'
   62 |  debug(a);
      |  ^~~~~
Main.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42
      |                    ^~
Main.cpp:77:3: note: in expansion of macro 'debug'
   77 |   debug(i, dp[i], a[i]);
      |   ^~~~~

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