Submission #420043

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
420043	2021-06-08T01:51:58 Z	iaNTU	Financial Report (JOI21_financial)	C++17	100 / 100	1059 ms	34564 KB

Main

// Exported by Exporter.exe

// Included from B.cpp
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define MTP make_tuple
#define R Read
#define RD Read_Digit
#define RP Read_P
#define RL Read_Loop
#define RLD Read_Loop_Digit
#define RLP Read_Loop_P
#ifdef ONLINE_JUDGE
	#define Debug(x) ;
	#define Debugln(x) ;
	#define Debug_Array(n,x) ;
	#define Debugln_Array(n,x) ;
	#define NL ;
#else
	#define Debug(x) printf("%s :", (#x)), _Debug(x)
	#define Debugln(x) printf("%s :", (#x)), _Debugln(x)
	#define Debug_Array(n,x) printf("%s :", (#x)), _Debug_Array((n), (x))
	#define Debugln_Array(n,x) printf("%s :", (#x)), _Debugln_Array((n), (x))
	#define NL printf("\n")
#endif
typedef long long int ll;
typedef unsigned long long int ull;

constexpr int kN = int(3E5 + 10);
// constexpr int kMod = 998244353;
// constexpr int kMod = int(1E9 + 7);
constexpr int kInf = 0x3f3f3f3f;
// constexpr ll kInf = 0x3f3f3f3f3f3f3f3f;
// constexpr double kPi = acos(-1);
// constexpr double kEps = 1E-9;


// Included from C:\Users\ianli\Desktop\CP\template\Various\Fast_IO\Fast_IO.cpp
// --- Get ---
static inline char Get_Raw_Char() {
	static char buf[1 << 16], *p = buf, *end = buf;
	if (p == end) {
		if ((end = buf + fread(buf, 1, 1 << 16, stdin)) == buf) return '\0';
		p = buf;
	}
	return *p++;
}

// --- Read ---
template <typename T> static inline void Read_P(T &n) {
	static_assert(is_integral<T>::value, "Read_P requires an integral type");
	char c;
	while (!isdigit(c = Get_Raw_Char())) ;
	n = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
	return ;
}

template <typename T> static inline void Read(T &n) {
	static_assert(is_integral<T>::value, "Read requires an integral type");
	char c;
	bool neg = false;
	while (!isdigit(c = Get_Raw_Char())) if (c == '-') neg = true;
	n = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
	if (neg) n = -n;
	return ;
}

template <typename T> static inline void Read_Digit(T &n) {
	static_assert(is_integral<T>::value, "Read_Digit requires an integral type");
	char c;
	while (!isdigit(c = Get_Raw_Char())) ;
	n = int(c - '0');
	return ;
}

// --- Read multiple ---
template <typename T, typename... Targs> static inline void Read(T &n, Targs&... Fargs) {Read(n); return Read(Fargs...);}
template <typename T, typename... Targs> static inline void Read_Digit(T &n, Targs&... Fargs) {Read_Digit(n); return Read_Digit(Fargs...);}
template <typename T, typename... Targs> static inline void Read_P(T &n, Targs&... Fargs) {Read_P(n); return Read_P(Fargs...);}

// --- Read Loop ---
template <typename T> static inline void Read_Loop_i(int i, T *a) {return Read(a[i]);}
template <typename T, typename... Targs> static inline void Read_Loop_i(int i, T *a, Targs*... Fargs) {Read(a[i]); return Read_Loop_i(i, Fargs...);}
template <typename... Targs> static inline void Read_Loop(int n, Targs*... Fargs) {for (int i = 1; i <= n; i++) Read_Loop_i(i, Fargs...);}

template <typename T> static inline void Read_Loop_Digit_i(int i, T *a) {return Read_Digit(a[i]);}
template <typename T, typename... Targs> static inline void Read_Loop_Digit_i(int i, T *a, Targs*... Fargs) {Read_Digit(a[i]); return Read_Loop_Digit_i(i, Fargs...);}
template <typename... Targs> static inline void Read_Loop_Digit(int n, Targs*... Fargs) {for (int i = 1; i <= n; i++) Read_Loop_Digit_i(i, Fargs...);}

template <typename T> static inline void Read_Loop_P_i(int i, T *a) {return Read_P(a[i]);}
template <typename T, typename... Targs> static inline void Read_Loop_P_i(int i, T *a, Targs*... Fargs) {Read_P(a[i]); return Read_Loop_P_i(i, Fargs...);}
template <typename... Targs> static inline void Read_Loop_P(int n, Targs*... Fargs) {for (int i = 1; i <= n; i++) Read_Loop_P_i(i, Fargs...);}

// --- Float ---
template <int mul, typename T> static inline void Read(T &n) {
	char c;
	bool neg = false;
	while (!isdigit(c = Get_Raw_Char())) if (c == '-') neg = true;
	n = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
	
	int cnt = 0;

	if (c == '.') {
		while (isdigit(c = Get_Raw_Char())) {
			n = n * 10 + int(c - '0');
			cnt++;
		}
	}

	while (cnt++ < mul) n = n * 10;

	if (neg) n = -n;
	return ;
}

template <int mul, typename T> static inline void Read_P(T &n) {
	char c;
	while (!isdigit(c = Get_Raw_Char())) ;
	
	n = int(c - '0');
	while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
	
	int cnt = 0;

	if (c == '.') {
		while (isdigit(c = Get_Raw_Char())) {
			n = n * 10 + int(c - '0');
			cnt++;
		}
	}

	while (cnt++ < mul) n = n * 10;
	return ;
}

template <int mul, typename T, typename... Targs> static inline void Read(T &n, Targs&... Fargs) {Read<mul>(n); return Read<mul>(Fargs...);}
template <int mul, typename T, typename... Targs> static inline void Read_P(T &n, Targs&... Fargs) {Read_P<mul>(n); return Read_P<mul>(Fargs...);}

// --- init ---
inline void IOS() {ios::sync_with_stdio(false); cin.tie(0); return ;}
inline void Freopen(const char *in, const char *out) {freopen(in, "r", stdin); freopen(out, "w", stdout); return ;}

// --- Output ---
template <typename T> void Print(T x) {
	if (x < 0) {
		printf("-");
		x = -x;
	}
	if (x == 0) printf("0");
	else {
		static int val[100];
		int idx = -1;
		while (x) {
			val[++idx] = x % 10;
			x /= 10;
		}
		while (idx >= 0) printf("%d", val[idx--]);
	}
} 
// End of C:\Users\ianli\Desktop\CP\template\Various\Fast_IO\Fast_IO.cpp

// Included from C:\Users\ianli\Desktop\CP\template\Various\Useful_Functions\Useful_Functions.cpp
template <typename T> inline void sort(vector<T> &v) {return sort(v.begin(), v.end());}
template <typename T> inline void sort_r(vector<T> &v) {return sort(v.begin(), v.end(), greater<T>());}

template <typename T> inline void reverse(vector<T> &v) {return reverse(v.begin(), v.end());}

template <typename T> inline void Merge(vector<T> &a, vector<T> &b, vector<T> &c) {
	if (c.size() < a.size() + b.size()) c.resize(a.size() + b.size());
	merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
	return ;
}
template <typename T> inline void Concatanate(vector<T> &a, vector<T> &b, vector<T> &c) {
	int a_size = int(a.size()), b_size = int(b.size());
	c.resize(a_size + b_size);
	for (int i = 0; i < a_size; i++) c[i] = a[i];
	for (int i = 0; i < b_size; i++) c[i + a_size] = b[i];
	return ;
}

template <typename T> inline void Discrete(vector<T> &v) {sort(v); v.resize(unique(v.begin(), v.end()) - v.begin()); return ;}

template <typename T> using PQ = priority_queue<T>;
template <typename T> using PQ_R = priority_queue<T, vector<T>, greater<T>>;

template <typename T> inline T ABS(T n) {return n >= 0 ? n : -n;}
template <typename T> __attribute__((target("bmi"))) inline T gcd(T a, T b) {
	if (a < 0) a = -a;
	if (b < 0) b = -b;
	if (a == 0 || b == 0) return a + b;
	int n = __builtin_ctzll(a);
	int m = __builtin_ctzll(b);
	a >>= n;
	b >>= m;
	while (a != b) {
		int m = __builtin_ctzll(a - b);
		bool f = a > b;
		T c = f ? a : b;
		b = f ? b : a;
		a = (c - b) >> m;
	}
	return a << min(n, m);
}
template <typename T> inline T lcm(T a, T b) {return a * b / gcd(a, b);}
template <typename T, typename... Targs> inline T gcd(T a, T b, T c, Targs... args) {return gcd(a, gcd(b, c, args...));}
template <typename T, typename... Targs> inline T lcm(T a, T b, T c, Targs... args) {return lcm(a, lcm(b, c, args...));}
template <typename T, typename... Targs> inline T min(T a, T b, T c, Targs... args) {return min(a, min(b, c, args...));}
template <typename T, typename... Targs> inline T max(T a, T b, T c, Targs... args) {return max(a, max(b, c, args...));}
template <typename T, typename... Targs> inline void chmin(T &a, T b, Targs... args) {a = min(a, b, args...); return ;}
template <typename T, typename... Targs> inline void chmax(T &a, T b, Targs... args) {a = max(a, b, args...); return ;}

vector<int> Primes(int n) {
	if (n == 1) return {};
	// 2 ~ n
	vector<int> primes;
	vector<bool> isPrime(n + 1, true);

	primes.reserve(n / __lg(n));

	for (int i = 2; i <= n; i++) {
		if (isPrime[i]) primes.push_back(i);
		for (int j : primes) {
			if (i * j > n) break;
			isPrime[i * j] = false;
			if (i % j == 0) break;
		}
	}
	return primes;
}

vector<int> factors(int x) {
	vector<int> ans;
	for (int i = 1; i * i <= x; i++) if (x % i == 0) ans.PB(i);

	int id = int(ans.size()) - 1;
	if (ans[id] * ans[id] == x) id--;
	for (int i = id; i >= 0; i--) ans.PB(x / ans[i]);

	return ans;
}

int mex(vector<int> vec) {
	int n = int(vec.size());
	vector<bool> have(n, false);
	for (int i : vec) if (i < n) have[i] = true;
	for (int i = 0; i < n; i++) if (!have[i]) return i;
	return n;
}

template <typename T> T SQ(T x) {return x * x;}

template <typename T> T Mdist(pair<T, T> lhs, pair<T, T> rhs) {return ABS(lhs.first - rhs.first) + ABS(lhs.second - rhs.second);}
template <typename T> T Dist2(pair<T, T> lhs, pair<T, T> rhs) {
	return SQ(lhs.F - rhs.F) + SQ(lhs.S - rhs.S);
}

template <typename T> T LUBound(T LB, T val, T UB) {return min(max(LB, val), UB);}

template <typename T, typename Comp> T Binary_Search(T L, T R, Comp f) {
	// L good R bad
	static_assert(is_integral<T>::value, "Binary_Search requires an integral type");
	while (R - L > 1) {
		T mid = (L + R) >> 1;
		if (f(mid)) L = mid;
		else R = mid;
	}
	return L;
}

template <typename Comp> double Binary_Search(double L, double R, Comp f, int n = 30) {
	for (int i = 1; i <= n; i++) {
		double mid = (L + R) / 2;
		if (f(mid)) L = mid;
		else R = mid;
	}
	return L;
}
// End of C:\Users\ianli\Desktop\CP\template\Various\Useful_Functions\Useful_Functions.cpp

// Included from C:\Users\ianli\Desktop\CP\template\Various\Debug\Debug.cpp
void _print(int x) {printf("%d", x);}
void _print(long long int x) {printf("%lld", x);}
void _print(unsigned long long int x) {printf("%llu", x);}
void _print(double x) {printf("%lf", x);}
template <typename T> void _print(T x) {return x.out();}
template <typename T1, typename T2> void _print(pair<T1, T2> x) {printf("("); _print(x.first); printf(", "); _print(x.second); printf(")");}

template <typename T> void _Debug(T x) {_print(x); printf("\n");}
template <typename T> void _Debug(vector<T> v) {
	if (v.empty()) printf(" empty");
	else for (T i : v) printf(" "), _print(i); 
	printf("\n");
}

template <typename T1, typename T2, typename T3> void _Debug(priority_queue<T1, T2, T3> pq) {
	if (pq.empty()) printf(" empty");
	else {
		while (!pq.empty()) {
			printf(" ");
			_print(pq.top());
			pq.pop();
		}
	}
	printf("\n");
}

template <typename T> void _Debug(queue<T> q) {
	if (q.empty()) printf(" empty");
	else {
		while (!q.empty()) {
			printf(" ");
			_print(q.front());
			q.pop();
		}
	}
	printf("\n");
}

template <typename T> void _Debug(stack<T> st) {
	if (st.empty()) printf(" empty");
	else {
		while (!st.empty()) {
			printf(" ");
			_print(st.top());
			st.pop();
		}
	}
	printf("\n");
}

template <typename T> void _Debug(deque<T> dq) {
	if (dq.empty()) printf(" empty");
	else {
		while (!dq.empty()) {
			printf(" ");
			_print(dq.front());
			dq.pop_front();
		}
	}
	printf("\n");
}

template <typename T> void _Debugln(vector<T> v) {
	if (v.empty()) printf(" empty\n");
	else {
		for (T i : v) printf("\n"), _print(i); 
		printf("\n");
	}
}

template <typename T1, typename T2, typename T3> void _Debugln(priority_queue<T1, T2, T3> pq) {
	if (pq.empty()) printf(" empty");
	else {
		while (!pq.empty()) {
			printf("\n");
			_print(pq.top());
			pq.pop();
		}
	}
	printf("\n");
}

template <typename T> void _Debugln(queue<T> q) {
	if (q.empty()) printf(" empty");
	else {
		while (!q.empty()) {
			printf("\n");
			_print(q.front());
			q.pop();
		}
	}
	printf("\n");
}

template <typename T> void _Debugln(stack<T> st) {
	if (st.empty()) printf(" empty");
	else {
		while (!st.empty()) {
			printf("\n");
			_print(st.top());
			st.pop();
		}
	}
	printf("\n");
}

template <typename T> void _Debugln(deque<T> dq) {
	if (dq.empty()) printf(" empty");
	else {
		while (!dq.empty()) {
			printf("\n");
			_print(dq.front());
			dq.pop_front();
		}
	}
	printf("\n");
}

template <typename T> void _Debug_Array(int n, const T *x) {for (int i = 1; i <= n; i++) printf(" "), _print(x[i]); printf("\n");}
template <typename T> void _Debugln_Array(int n, const T *x) {printf("\n"); for (int i = 1; i <= n; i++) _print(x[i]), printf("\n");}
// End of C:\Users\ianli\Desktop\CP\template\Various\Debug\Debug.cpp

// Included from C:\Users\ianli\Desktop\CP\template\DS\Seg_tree\max.cpp
// range add, max
template <typename T> struct seg_tree_max {
	static constexpr T kInf = numeric_limits<T>::max() / 2 - 10;
	private :
	int _size;
	T *val, *flag;

	void addtag(int n, T x) {
		val[n] += x;
		flag[n] += x;
		return ;
	}
	void push(int n) {
		if (flag[n]) {
			addtag(n << 1, flag[n]);
			addtag(n << 1 | 1, flag[n]);
			flag[n] = 0;
		}
		return ;
	}
	void pull(int n) {
		val[n] = max(val[n << 1], val[n << 1 | 1]);
		return ;
	}

	void init(int n, int l, int r) {
		val[n] = -kInf;
		flag[n] = 0;
		if (l < r) {
			int mid = (l + r) >> 1;
			init(n << 1, l, mid);
			init(n << 1 | 1, mid + 1, r);
		}
		return ;
	}

	void init(int n, int l, int r, T *v) {
		flag[n] = 0;
		if (l == r) val[n] = v[l];
		else {
			int mid = (l + r) >> 1;
			init(n << 1, l, mid, v);
			init(n << 1 | 1, mid + 1, r, v);
			pull(n);
		}
		return ;
	}

	void set(int n, int l, int r, int pos, T x) {
		if (l == r) val[n] = x;
		else {
			int mid = (l + r) >> 1;
			push(n);
			if (pos <= mid) set(n << 1, l, mid, pos, x);
			else set(n << 1 | 1, mid + 1, r, pos, x);
			pull(n);
		}
		return ;
	}
	void add(int n, int l, int r, int L, int R, T x) {
		if (L <= l && r <= R) addtag(n, x);
		else if (!(L > r || l > R)) {
			int mid = (l + r) >> 1;
			push(n);
			add(n << 1, l, mid, L, R, x);
			add(n << 1 | 1, mid + 1, r, L, R, x);
			pull(n);
		}
		return ;
	}
	void fix(int n, int l, int r, int pos, T x) {
		chmax(val[n], x);
		if (l < r) {
			int mid = (l + r) >> 1;
			push(n);
			if (pos <= mid) fix(n << 1, l, mid, pos, x);
			else fix(n << 1 | 1, mid + 1, r, pos, x);
		}
		return ;
	}

	T ask(int n, int l, int r, int pos) {
		if (l == r) return val[n];
		else {
			int mid = (l + r) >> 1;
			push(n);
			if (pos <= mid) return ask(n << 1, l, mid, pos);
			else return ask(n << 1 | 1, mid + 1, r, pos);
		}
	}
	T ask(int n, int l, int r, int L, int R) {
		if (L <= l && r <= R) return val[n];
		else if (l > R || L > r) return -kInf;
		else {
			int mid = (l + r) >> 1;
			push(n);
			return max(ask(n << 1, l, mid, L, R), ask(n << 1 | 1, mid + 1, r, L, R));
		}
	}

	public:
	seg_tree_max() : _size(0), val(nullptr), flag(nullptr) {}
	void init(int n) {
		delete [] val; val = new T [n << 2];
		delete [] flag; flag = new T [n << 2];
		return init(1, 1, _size = n);
	}
	void init(int n, T *v) {
		delete [] val; val = new T [n << 2];
		delete [] flag; flag = new T [n << 2];
		return init(1, 1, _size = n, v);
	}
	void set(int pos, T x) {return set(1, 1, _size, pos, x);}
	// void add(int pos, T x)
	void add(int L, int R, T x) {return add(1, 1, _size, L, R, x);}
	void fix(int pos, T x) {return fix(1, 1, _size, pos, x);}
	// fix = take max
	T ask(int pos) {return ask(1, 1, _size, pos);}
	T ask(int L, int R) {return ask(1, 1, _size, L, R);}
	T top() const {return val[1];}
};

// End of C:\Users\ianli\Desktop\CP\template\DS\Seg_tree\max.cpp

// Included from C:\Users\ianli\Desktop\CP\template\DS\Seg_tree\rsa_id_max.cpp
// range set, add, max, id
// !!! If exist multiple max values then it would return any of them (not necessarily leftmost/rightmost)
template <typename T> struct seg_tree_rsa_id_max {
	static constexpr T kInf = numeric_limits<T>::max() / 2 - 10;
	private :
	int _size;
	pair<T, int> *_val;
	T *_set_flag, *_add_flag;
	vector<bool> _has_set_flag;

	void addtag(int n, T x) {
		_val[n].first += x;
		_add_flag[n] += x;
		return ;
	}
	void settag(int n, T x) {
		_val[n].first = x;
		_set_flag[n] = x;
		_add_flag[n] = 0;
		_has_set_flag[n] = true;
		return ;
	}
	void push(int n) {
		if (_has_set_flag[n]) {
			settag(n << 1, _set_flag[n]);
			settag(n << 1 | 1, _set_flag[n]);
			_has_set_flag[n] = false;
		}
		if (_add_flag[n]) {
			addtag(n << 1, _add_flag[n]);
			addtag(n << 1 | 1, _add_flag[n]);
			_add_flag[n] = 0;
		}
		return ;
	}
	void pull(int n) {
		_val[n] = max(_val[n << 1], _val[n << 1 | 1]);
		return ;
	}

	void init(int n, int l, int r) {
		_val[n] = make_pair(-kInf, r);
		_has_set_flag[n] = false;
		_add_flag[n] = 0;
		if (l < r) {
			int mid = (l + r) >> 1;
			init(n << 1, l, mid);
			init(n << 1 | 1, mid + 1, r);
		}
		return ;
	}

	void init(int n, int l, int r, T *v) {
		_has_set_flag[n] = false;
		_add_flag[n] = 0;
		if (l == r) _val[n] = make_pair(v[l], l);
		else {
			int mid = (l + r) >> 1;
			init(n << 1, l, mid, v);
			init(n << 1 | 1, mid + 1, r, v);
			pull(n);
		}
		return ;
	}

	void set(int n, int l, int r, int pos, T x) {
		if (l == r) _val[n].first = x;
		else {
			int mid = (l + r) >> 1;
			push(n);
			if (pos <= mid) set(n << 1, l, mid, pos, x);
			else set(n << 1 | 1, mid + 1, r, pos, x);
			pull(n);
		}
		return ;
	}
	void set(int n, int l, int r, int L, int R, T x) {
		if (L <= l && r <= R) settag(n, x);
		else if (!(l > R || L > r)) {
			int mid = (l + r) >> 1;
			push(n);
			set(n << 1, l, mid, L, R, x);
			set(n << 1 | 1, mid + 1, r, L, R, x);
			pull(n);
		}
		return ;
	}

	void add(int n, int l, int r, int pos, T x) {
		if (l == r) _val[n].first += x;
		else {
			int mid = (l + r) >> 1;
			push(n);
			if (pos <= mid) add(n << 1, l, mid, pos, x);
			else add(n << 1 | 1, mid + 1, r, pos, x);
			pull(n);
		}
		return ;
	}
	void add(int n, int l, int r, int L, int R, T x) {
		if (L <= l && r <= R) addtag(n, x);
		else if (!(l > R || L > r)) {
			int mid = (l + r) >> 1;
			push(n);
			add(n << 1, l, mid, L, R, x);
			add(n << 1 | 1, mid + 1, r, L, R, x);
			pull(n);
		}
		return ;
	}

	pair<T, int> ask(int n, int l, int r, int pos) {
		if (l == r) return _val[n];
		else {
			int mid = (l + r) >> 1;
			push(n);
			if (pos <= mid) return ask(n << 1, l, mid, pos);
			else return ask(n << 1 | 1, mid + 1, r, pos);
		}
	}
	pair<T, int> ask(int n, int l, int r, int L, int R) {
		if (L <= l && r <= R) return _val[n];
		else if (l > R || L > r) return -kInf;
		else {
			int mid = (l + r) >> 1;
			push(n);
			return max(ask(n << 1, l, mid, L, R), ask(n << 1 | 1, mid + 1, r, L, R));
		}
	}

	public:
	seg_tree_rsa_id_max() : _size(0), _val(nullptr), _add_flag(nullptr), _set_flag(nullptr) {}
	void init(int n) {
		delete [] _val; _val = new pair<T, int> [n << 2];
		delete [] _add_flag; _add_flag = new T [n << 2];
		delete [] _set_flag; _set_flag = new T [n << 2];
		_has_set_flag.resize(n << 2);
		return init(1, 1, _size = n);
	}
	void init(int n, T *v) {
		delete [] _val; _val = new pair<T, int> [n << 2];
		delete [] _add_flag; _add_flag = new T [n << 2];
		delete [] _set_flag; _set_flag = new T [n << 2];
		_has_set_flag.resize(n << 2);
		return init(1, 1, _size = n, v);
	}
	void set(int pos, T x) {return set(1, 1, _size, pos, x);}
	void set(int L, int R, T x) {return set(1, 1, _size, L, R, x);}
	void add(int pos, T x) {return add(1, 1, _size, pos, x);}
	void add(int L, int R, T x) {return add(1, 1, _size, L, R, x);}
	pair<T, int> ask(int pos) {return ask(1, 1, _size, pos);}
	pair<T, int> ask(int L, int R) {return ask(1, 1, _size, L, R);}
	pair<T, int> top() const {return _val[1];}
};

// End of C:\Users\ianli\Desktop\CP\template\DS\Seg_tree\rsa_id_max.cpp

seg_tree_max<int> sg_dp;
seg_tree_rsa_id_max<int> sg_d;
int dp[kN];
int a[kN];
pair<int, int> p[kN];

int main() {
	int n, d; RP(n, d);
	RLP(n, a);

	for (int i = 1; i <= n; i++) p[i] = MP(a[i], -i);
	sort(p + 1, p + n + 1);
	for (int i = 1; i <= n; i++) a[-p[i].S] = i;

	sg_dp.init(n);
	sg_d.init(n);
	sg_d.set(1, n, -kInf);

	//Debug_Array(n, a);

	PQ<pair<int, int>> pq;
	for (int i = 1; i <= n; i++) {
		//Debug(i);
		dp[i] = max(1, sg_dp.ask(1, a[i] - 1) + 1);
		sg_d.add(1, a[i] - 1, 1);
		int counter = 1;
		while (!pq.empty() && pq.top().F >= a[i]) {
			sg_d.add(a[i], pq.top().F, -pq.top().S);
			counter += pq.top().S;
			pq.pop();
		}
		pq.push(MP(a[i] - 1, counter));

		//sg_d.set(a[i], n, 0);
		while (sg_d.top().F >= d) {
			int id = sg_d.top().S;
			sg_d.set(id, -kInf);
			sg_dp.set(id, -kInf);
			//Debug(id);
		}
		sg_d.set(a[i], 0);
		sg_dp.set(a[i], dp[i]);
	}

	//Debug_Array(n, dp);

	int ans = 0;
	for (int i = 1; i <= n; i++) chmax(ans, dp[i]);
	printf("%d\n", ans);
}
// End of B.cpp

Compilation message

Main.cpp: In instantiation of 'seg_tree_rsa_id_max<T>::seg_tree_rsa_id_max() [with T = int]':
Main.cpp:694:26:   required from here
Main.cpp:543:17: warning: 'seg_tree_rsa_id_max<int>::_add_flag' will be initialized after [-Wreorder]
  543 |  T *_set_flag, *_add_flag;
      |                 ^~~~~~~~~
Main.cpp:543:5: warning:   'int* seg_tree_rsa_id_max<int>::_set_flag' [-Wreorder]
  543 |  T *_set_flag, *_add_flag;
      |     ^~~~~~~~~
Main.cpp:667:2: warning:   when initialized here [-Wreorder]
  667 |  seg_tree_rsa_id_max() : _size(0), _val(nullptr), _add_flag(nullptr), _set_flag(nullptr) {}
      |  ^~~~~~~~~~~~~~~~~~~

Subtask #1

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	288 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	0 ms	204 KB	Output is correct
20	Correct	0 ms	204 KB	Output is correct
21	Correct	0 ms	204 KB	Output is correct
22	Correct	0 ms	204 KB	Output is correct
23	Correct	0 ms	204 KB	Output is correct
24	Correct	0 ms	204 KB	Output is correct
25	Correct	1 ms	204 KB	Output is correct
26	Correct	1 ms	204 KB	Output is correct

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	288 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	0 ms	204 KB	Output is correct
20	Correct	0 ms	204 KB	Output is correct
21	Correct	0 ms	204 KB	Output is correct
22	Correct	0 ms	204 KB	Output is correct
23	Correct	0 ms	204 KB	Output is correct
24	Correct	0 ms	204 KB	Output is correct
25	Correct	1 ms	204 KB	Output is correct
26	Correct	1 ms	204 KB	Output is correct
27	Correct	1 ms	332 KB	Output is correct
28	Correct	1 ms	332 KB	Output is correct
29	Correct	1 ms	332 KB	Output is correct
30	Correct	1 ms	332 KB	Output is correct
31	Correct	1 ms	332 KB	Output is correct
32	Correct	1 ms	332 KB	Output is correct
33	Correct	1 ms	332 KB	Output is correct
34	Correct	1 ms	332 KB	Output is correct
35	Correct	1 ms	332 KB	Output is correct
36	Correct	1 ms	332 KB	Output is correct
37	Correct	1 ms	332 KB	Output is correct
38	Correct	1 ms	332 KB	Output is correct
39	Correct	1 ms	332 KB	Output is correct
40	Correct	1 ms	332 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	288 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	0 ms	204 KB	Output is correct
20	Correct	0 ms	204 KB	Output is correct
21	Correct	0 ms	204 KB	Output is correct
22	Correct	0 ms	204 KB	Output is correct
23	Correct	0 ms	204 KB	Output is correct
24	Correct	0 ms	204 KB	Output is correct
25	Correct	1 ms	204 KB	Output is correct
26	Correct	1 ms	204 KB	Output is correct
27	Correct	1 ms	332 KB	Output is correct
28	Correct	1 ms	332 KB	Output is correct
29	Correct	1 ms	332 KB	Output is correct
30	Correct	1 ms	332 KB	Output is correct
31	Correct	1 ms	332 KB	Output is correct
32	Correct	1 ms	332 KB	Output is correct
33	Correct	1 ms	332 KB	Output is correct
34	Correct	1 ms	332 KB	Output is correct
35	Correct	1 ms	332 KB	Output is correct
36	Correct	1 ms	332 KB	Output is correct
37	Correct	1 ms	332 KB	Output is correct
38	Correct	1 ms	332 KB	Output is correct
39	Correct	1 ms	332 KB	Output is correct
40	Correct	1 ms	332 KB	Output is correct
41	Correct	15 ms	980 KB	Output is correct
42	Correct	15 ms	968 KB	Output is correct
43	Correct	11 ms	976 KB	Output is correct
44	Correct	11 ms	932 KB	Output is correct
45	Correct	11 ms	972 KB	Output is correct
46	Correct	12 ms	984 KB	Output is correct
47	Correct	14 ms	972 KB	Output is correct
48	Correct	14 ms	968 KB	Output is correct
49	Correct	13 ms	964 KB	Output is correct
50	Correct	13 ms	996 KB	Output is correct
51	Correct	13 ms	972 KB	Output is correct
52	Correct	15 ms	980 KB	Output is correct
53	Correct	10 ms	1020 KB	Output is correct
54	Correct	12 ms	972 KB	Output is correct
55	Correct	11 ms	972 KB	Output is correct
56	Correct	10 ms	972 KB	Output is correct
57	Correct	11 ms	972 KB	Output is correct
58	Correct	7 ms	972 KB	Output is correct
59	Correct	7 ms	984 KB	Output is correct
60	Correct	11 ms	972 KB	Output is correct
61	Correct	9 ms	976 KB	Output is correct

Subtask #4

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	399 ms	30920 KB	Output is correct
2	Correct	709 ms	31032 KB	Output is correct
3	Correct	887 ms	31000 KB	Output is correct
4	Correct	1033 ms	30960 KB	Output is correct
5	Correct	862 ms	30956 KB	Output is correct
6	Correct	1033 ms	31004 KB	Output is correct
7	Correct	433 ms	34472 KB	Output is correct
8	Correct	411 ms	30848 KB	Output is correct
9	Correct	496 ms	32772 KB	Output is correct
10	Correct	500 ms	31008 KB	Output is correct
11	Correct	818 ms	30916 KB	Output is correct
12	Correct	853 ms	30948 KB	Output is correct
13	Correct	873 ms	31028 KB	Output is correct
14	Correct	975 ms	30980 KB	Output is correct

Subtask #5

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	411 ms	30928 KB	Output is correct
2	Correct	680 ms	30880 KB	Output is correct
3	Correct	779 ms	31008 KB	Output is correct
4	Correct	801 ms	31024 KB	Output is correct
5	Correct	738 ms	31000 KB	Output is correct
6	Correct	784 ms	31108 KB	Output is correct
7	Correct	319 ms	34564 KB	Output is correct
8	Correct	409 ms	31012 KB	Output is correct
9	Correct	452 ms	31468 KB	Output is correct
10	Correct	619 ms	30876 KB	Output is correct
11	Correct	753 ms	30916 KB	Output is correct
12	Correct	664 ms	31208 KB	Output is correct

Subtask #6

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	288 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	0 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	0 ms	204 KB	Output is correct
20	Correct	0 ms	204 KB	Output is correct
21	Correct	0 ms	204 KB	Output is correct
22	Correct	0 ms	204 KB	Output is correct
23	Correct	0 ms	204 KB	Output is correct
24	Correct	0 ms	204 KB	Output is correct
25	Correct	1 ms	204 KB	Output is correct
26	Correct	1 ms	204 KB	Output is correct
27	Correct	1 ms	332 KB	Output is correct
28	Correct	1 ms	332 KB	Output is correct
29	Correct	1 ms	332 KB	Output is correct
30	Correct	1 ms	332 KB	Output is correct
31	Correct	1 ms	332 KB	Output is correct
32	Correct	1 ms	332 KB	Output is correct
33	Correct	1 ms	332 KB	Output is correct
34	Correct	1 ms	332 KB	Output is correct
35	Correct	1 ms	332 KB	Output is correct
36	Correct	1 ms	332 KB	Output is correct
37	Correct	1 ms	332 KB	Output is correct
38	Correct	1 ms	332 KB	Output is correct
39	Correct	1 ms	332 KB	Output is correct
40	Correct	1 ms	332 KB	Output is correct
41	Correct	15 ms	980 KB	Output is correct
42	Correct	15 ms	968 KB	Output is correct
43	Correct	11 ms	976 KB	Output is correct
44	Correct	11 ms	932 KB	Output is correct
45	Correct	11 ms	972 KB	Output is correct
46	Correct	12 ms	984 KB	Output is correct
47	Correct	14 ms	972 KB	Output is correct
48	Correct	14 ms	968 KB	Output is correct
49	Correct	13 ms	964 KB	Output is correct
50	Correct	13 ms	996 KB	Output is correct
51	Correct	13 ms	972 KB	Output is correct
52	Correct	15 ms	980 KB	Output is correct
53	Correct	10 ms	1020 KB	Output is correct
54	Correct	12 ms	972 KB	Output is correct
55	Correct	11 ms	972 KB	Output is correct
56	Correct	10 ms	972 KB	Output is correct
57	Correct	11 ms	972 KB	Output is correct
58	Correct	7 ms	972 KB	Output is correct
59	Correct	7 ms	984 KB	Output is correct
60	Correct	11 ms	972 KB	Output is correct
61	Correct	9 ms	976 KB	Output is correct
62	Correct	399 ms	30920 KB	Output is correct
63	Correct	709 ms	31032 KB	Output is correct
64	Correct	887 ms	31000 KB	Output is correct
65	Correct	1033 ms	30960 KB	Output is correct
66	Correct	862 ms	30956 KB	Output is correct
67	Correct	1033 ms	31004 KB	Output is correct
68	Correct	433 ms	34472 KB	Output is correct
69	Correct	411 ms	30848 KB	Output is correct
70	Correct	496 ms	32772 KB	Output is correct
71	Correct	500 ms	31008 KB	Output is correct
72	Correct	818 ms	30916 KB	Output is correct
73	Correct	853 ms	30948 KB	Output is correct
74	Correct	873 ms	31028 KB	Output is correct
75	Correct	975 ms	30980 KB	Output is correct
76	Correct	411 ms	30928 KB	Output is correct
77	Correct	680 ms	30880 KB	Output is correct
78	Correct	779 ms	31008 KB	Output is correct
79	Correct	801 ms	31024 KB	Output is correct
80	Correct	738 ms	31000 KB	Output is correct
81	Correct	784 ms	31108 KB	Output is correct
82	Correct	319 ms	34564 KB	Output is correct
83	Correct	409 ms	31012 KB	Output is correct
84	Correct	452 ms	31468 KB	Output is correct
85	Correct	619 ms	30876 KB	Output is correct
86	Correct	753 ms	30916 KB	Output is correct
87	Correct	664 ms	31208 KB	Output is correct
88	Correct	977 ms	30904 KB	Output is correct
89	Correct	1059 ms	30996 KB	Output is correct
90	Correct	1014 ms	31128 KB	Output is correct
91	Correct	849 ms	31064 KB	Output is correct
92	Correct	641 ms	30996 KB	Output is correct
93	Correct	796 ms	31084 KB	Output is correct
94	Correct	777 ms	31188 KB	Output is correct
95	Correct	943 ms	31008 KB	Output is correct
96	Correct	964 ms	31104 KB	Output is correct
97	Correct	963 ms	30960 KB	Output is correct
98	Correct	826 ms	30928 KB	Output is correct
99	Correct	787 ms	30920 KB	Output is correct
100	Correct	784 ms	31104 KB	Output is correct
101	Correct	549 ms	32088 KB	Output is correct
102	Correct	624 ms	31296 KB	Output is correct
103	Correct	662 ms	31016 KB	Output is correct
104	Correct	731 ms	31000 KB	Output is correct
105	Correct	801 ms	30992 KB	Output is correct
106	Correct	595 ms	31152 KB	Output is correct
107	Correct	641 ms	31012 KB	Output is correct
108	Correct	734 ms	31164 KB	Output is correct
109	Correct	828 ms	31248 KB	Output is correct
110	Correct	846 ms	31004 KB	Output is correct
111	Correct	803 ms	30880 KB	Output is correct
112	Correct	712 ms	31092 KB	Output is correct
113	Correct	773 ms	31060 KB	Output is correct
114	Correct	781 ms	31012 KB	Output is correct
115	Correct	411 ms	31008 KB	Output is correct
116	Correct	407 ms	31020 KB	Output is correct
117	Correct	453 ms	30916 KB	Output is correct
118	Correct	446 ms	30916 KB	Output is correct
119	Correct	628 ms	31172 KB	Output is correct
120	Correct	628 ms	31000 KB	Output is correct