제출 #800100

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
800100		NothingXD	Financial Report (JOI21_financial)	C++17	100 / 100	3640 ms	288928 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 3e5 + 10;
const int lg = 22;

struct Seg{
	int l, r, ans;
	bool b;
} seg[maxn*lg];

int n, d, a[maxn], dp[maxn], lc[maxn*lg], rc[maxn*lg], root[maxn], vercnt = 1;
vector<pii> val;
void build(int v, int l, int r){
	seg[v].l = seg[v].r = seg[v].b = seg[v].ans = 0;
	if (l + 1 == r){
		return;
	}
	int mid = (l + r) >> 1;
	lc[v] = vercnt++;
	rc[v] = vercnt++;
	build(lc[v], l, mid);
	build(rc[v], mid, r);
}

Seg operator +(Seg a, Seg b){
	Seg res;
	res.l = (a.b? a.l + b.l: a.l);
	res.r = (b.b? b.r + a.r: b.r);
	res.ans = max({a.ans, b.ans, a.r + b.l});
	res.b = (a.b && b.b);
	return res;
}

void change(int v, int newv, int l, int r, int idx){
	if (l + 1 == r){
		seg[newv].l = seg[newv].r = seg[newv].ans = seg[newv].b = 1;
		return;
	}
	int mid = (l + r) >> 1;
	if (idx < mid){
		lc[newv] = vercnt++;
		rc[newv] = rc[v];
		change(lc[v], lc[newv], l, mid, idx);
	}
	else{
		lc[newv] = lc[v];
		rc[newv] = vercnt++;
		change(rc[v], rc[newv], mid, r, idx);
	}
	seg[newv] = seg[lc[newv]] + seg[rc[newv]];
}

Seg get(int v, int l, int r, int ql, int qr){
	if (qr <= l || r <= ql){
		Seg tmp;
		tmp.l = tmp.r = tmp.ans = 0;
		tmp.b = true;
		return tmp;
	}
	if (ql <= l && r <= qr) return seg[v];
	int mid = (l + r) >> 1;
	return get(lc[v], l, mid, ql, qr)
		+ get(rc[v], mid, r, ql, qr);
}

vector<int> num[maxn << 2];
vector<int> mx[maxn << 2];
bool ok[maxn << 2];

void add(int v, int l, int r, int idx){
	if (idx < l || r <= idx) return;
	if (l + 1 == r){
		num[v].resize(1);
		mx[v].resize(1);
		num[v][0] = (a[idx]);
		mx[v][0] = (dp[idx]);
		ok[v] = true;
		return;
	}
	int mid = (l + r) >> 1;
	add(v << 1, l, mid, idx);
	add(v << 1 | 1, mid, r, idx);
	if (!ok[v<<1] || !ok[v<<1|1]) return;
	ok[v] = true;
	int ptl = 0, ptr = 0;
	num[v].resize(r-l);
	mx[v].resize(r-l);
	for (int i = 0; i < r-l; i++){
		if (ptr == num[v<<1|1].size() || (ptl != num[v << 1].size() && num[v<<1][ptl] < num[v<<1|1][ptr])){
			num[v][i] = num[v<<1][ptl];
			mx[v][i] = mx[v<<1][ptl];
			ptl++;
		}
		else{
			num[v][i] = num[v<<1|1][ptr];
			mx[v][i] = mx[v<<1|1][ptr];
			ptr++;
		}
	}
	for (int i = 1; i < r-l; i++){
		mx[v][i] = max(mx[v][i], mx[v][i-1]);
	}
}

int get(int v, int l, int r, int ql, int qr, int val){
	if (qr <= l || r <= ql) return 0;
	if (ql <= l && r <= qr && ok[v]){
		int idx = lower_bound(all(num[v]), val) - num[v].begin();
		if (idx != 0) return mx[v][idx-1];
		return 0;
	}
	int mid = (l + r) >> 1;
	return max(get(v << 1, l, mid, ql, qr, val)
			,get(v << 1 | 1, mid, r, ql, qr, val));
}

int main(){

	cin >> n >> d;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		val.push_back({a[i], i});
	}

	sort(all(val));

	root[n] = 0;
	build(0, 1, n+1);

	//debug(vercnt);

	for (int i = n-1; ~i; i--){
		root[i] = vercnt++;
		//debug(i, val[i].S);
		change(root[i+1], root[i], 1, n+1, val[i].S);
		//debug(vercnt);
	}

	int ans = 0;

	for (int i = 1; i <= n; i++){
		int idx = lower_bound(all(val), MP(a[i], 0)) - val.begin();
		//debug(i, idx);
		int l = 0, r = i;
		while (l + 1 < r){
			int mid = (l + r) >> 1;
		//	debug(mid, get(root[idx], 1, n+1, mid, i).ans);
			if (get(root[idx], 1, n+1, mid, i).ans < d) r = mid;
			else l = mid;
		}
	//	debug(r);
		dp[i] = get(1, 1, n+1, r, i, a[i]) + 1;
	//	debug(i, dp[i]);
		add(1, 1, n+1, i);
		ans = max(ans, dp[i]);
	}

//	debug(vercnt);

	cout << ans << '\n';

	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void build(int, int, int)':
Main.cpp:33:46: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   33 |  seg[v].l = seg[v].r = seg[v].b = seg[v].ans = 0;
      |                                   ~~~~~~~~~~~^~~
Main.cpp: In function 'void add(int, int, int, int)':
Main.cpp:108:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |   if (ptr == num[v<<1|1].size() || (ptl != num[v << 1].size() && num[v<<1][ptl] < num[v<<1|1][ptr])){
      |       ~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:108:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |   if (ptr == num[v<<1|1].size() || (ptl != num[v << 1].size() && num[v<<1][ptl] < num[v<<1|1][ptr])){
      |                                     ~~~~^~~~~~~~~~~~~~~~~~~~~

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