답안 #420036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420036	2021-06-08T01:24:42 Z	iaNTU	Financial Report (JOI21_financial)	C++17	53 / 100	4000 ms	31124 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, 0);

	//Debug_Array(n, a);

	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);
		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_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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 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	1 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	1 ms	204 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	1 ms	204 KB	Output is correct
23	Correct	1 ms	204 KB	Output is correct
24	Correct	1 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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 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	1 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	1 ms	204 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	1 ms	204 KB	Output is correct
23	Correct	1 ms	204 KB	Output is correct
24	Correct	1 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	6 ms	332 KB	Output is correct
28	Correct	2 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	3 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	356 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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 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	1 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	1 ms	204 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	1 ms	204 KB	Output is correct
23	Correct	1 ms	204 KB	Output is correct
24	Correct	1 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	6 ms	332 KB	Output is correct
28	Correct	2 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	3 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	356 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	2216 ms	964 KB	Output is correct
42	Correct	1083 ms	1072 KB	Output is correct
43	Correct	242 ms	1092 KB	Output is correct
44	Correct	38 ms	936 KB	Output is correct
45	Correct	8 ms	968 KB	Output is correct
46	Correct	8 ms	992 KB	Output is correct
47	Correct	435 ms	928 KB	Output is correct
48	Correct	179 ms	944 KB	Output is correct
49	Correct	25 ms	968 KB	Output is correct
50	Correct	10 ms	984 KB	Output is correct
51	Correct	96 ms	936 KB	Output is correct
52	Correct	578 ms	964 KB	Output is correct
53	Correct	8 ms	972 KB	Output is correct
54	Correct	9 ms	944 KB	Output is correct
55	Correct	9 ms	972 KB	Output is correct
56	Correct	8 ms	972 KB	Output is correct
57	Correct	11 ms	972 KB	Output is correct
58	Correct	6 ms	964 KB	Output is correct
59	Correct	6 ms	972 KB	Output is correct
60	Correct	7 ms	968 KB	Output is correct
61	Correct	7 ms	972 KB	Output is correct

Subtask #4

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	478 ms	31020 KB	Output is correct
2	Execution timed out	4086 ms	29768 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #5

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	349 ms	30968 KB	Output is correct
2	Correct	490 ms	30884 KB	Output is correct
3	Correct	605 ms	30932 KB	Output is correct
4	Correct	655 ms	30964 KB	Output is correct
5	Correct	617 ms	31084 KB	Output is correct
6	Correct	600 ms	31012 KB	Output is correct
7	Correct	334 ms	30984 KB	Output is correct
8	Correct	333 ms	30924 KB	Output is correct
9	Correct	355 ms	30916 KB	Output is correct
10	Correct	448 ms	30860 KB	Output is correct
11	Correct	582 ms	31124 KB	Output is correct
12	Correct	579 ms	31008 KB	Output is correct

Subtask #6

0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 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	1 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	1 ms	204 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	1 ms	204 KB	Output is correct
23	Correct	1 ms	204 KB	Output is correct
24	Correct	1 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	6 ms	332 KB	Output is correct
28	Correct	2 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	3 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	356 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	2216 ms	964 KB	Output is correct
42	Correct	1083 ms	1072 KB	Output is correct
43	Correct	242 ms	1092 KB	Output is correct
44	Correct	38 ms	936 KB	Output is correct
45	Correct	8 ms	968 KB	Output is correct
46	Correct	8 ms	992 KB	Output is correct
47	Correct	435 ms	928 KB	Output is correct
48	Correct	179 ms	944 KB	Output is correct
49	Correct	25 ms	968 KB	Output is correct
50	Correct	10 ms	984 KB	Output is correct
51	Correct	96 ms	936 KB	Output is correct
52	Correct	578 ms	964 KB	Output is correct
53	Correct	8 ms	972 KB	Output is correct
54	Correct	9 ms	944 KB	Output is correct
55	Correct	9 ms	972 KB	Output is correct
56	Correct	8 ms	972 KB	Output is correct
57	Correct	11 ms	972 KB	Output is correct
58	Correct	6 ms	964 KB	Output is correct
59	Correct	6 ms	972 KB	Output is correct
60	Correct	7 ms	968 KB	Output is correct
61	Correct	7 ms	972 KB	Output is correct
62	Correct	478 ms	31020 KB	Output is correct
63	Execution timed out	4086 ms	29768 KB	Time limit exceeded
64	Halted	0 ms	0 KB	-