Submission #1248849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248849		nlsosad	Financial Report (JOI21_financial)	C++20	14 / 100	4109 ms	272596 KiB

Main

#include <bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
int a[300005];

struct Node{
	int pre, suf, sum, best;
};
int inf = -1e18;
Node merge(Node p, Node q){
	Node c;
	if(p.pre == inf and p.suf==inf and p.sum==inf){
		return q;
	}
	if(q.pre == inf and q.suf==inf and q.sum == inf){
		return p;
	}
	c.pre = max({p.pre, p.sum + q.pre, p.sum + q.sum});
	c.suf = max({q.suf, q.sum + p.suf, p.sum + q.sum});
	c.sum = p.sum + q.sum;
	c.best = max({c.pre, c.suf, c.sum, p.suf + q.pre, p.best, q.best});
	return c;
}
Node tr[1200001];
void build(int node, int l, int r){
	if(l==r){
		tr[node] = {inf, inf, inf, inf};
	}else{
		int mid = (l+r)/2;
		build(2*node, l, mid);
		build(2*node+1, mid+1, r);
		tr[node] = merge(tr[2*node], tr[2*node+1]);
	}
}
void update(int node, int l, int r, int p){
	if(l==r){
		tr[node] = {1, 1, 1, 1};
	}else{
		int mid = (l+r)/2;
		if(p<=mid){
			update(2*node, l, mid, p);
		}else update(2*node+1, mid+1, r, p);
		tr[node] = merge(tr[2*node], tr[2*node+1]);
	}
}
Node query(int node, int start, int end, int l, int r){
	if(start > r or end < l){
		return {inf, inf, inf, inf};
	}
	if(l<=start and end<=r){
		return tr[node];
	}
	int mid = (start+end)/2;
	Node t = query(2*node, start, mid, l, r);
	Node p = query(2*node+1, mid+1, end, l, r);
	return merge(t, p);
}

struct fenwick{
	int maxn;
	vector<int> bit;
	void resi(int m){
		maxn = m;
		bit.resize(m+1, 0);
	}
	void update(int id, int x){
		while(id<=maxn){
			bit[id] = max(bit[id], x);
			id += (id & (-id));
		}
	}
	int query(int id){
		int res = 0;
		while(id>0){
			res = max(res, bit[id]);
			id -= (id & (-id));
		}
		return res;
	}
};

vector<int> mtr[1200001];
fenwick cay[1200001];

void mmerge(vector<int> &a, vector<int> &b, vector<int> &c){
	int i = 1;
	int j = 1;
	while (i<a.size() and j < b.size()){
		if(a[i] > b[j]){
			c.push_back(a[i]);
			i++;
		}else{
			c.push_back(b[j]);
			j++;
		}
	}
	while(i<a.size()){
		c.push_back(a[i]);
		i++;
	}
	while(j<b.size()){
		c.push_back(b[j]);
		j++;
	}
}
void mbuild(int node, int l, int r){
	if(l==r){
		mtr[node].push_back(0);
		mtr[node].push_back(a[l]);
		cay[node].resi(1);
	}else{
		int mid = (l+r)/2;
		mbuild(2*node, l, mid);
		mbuild(2*node+1, mid+1, r);
		mtr[node].push_back(0);
		mmerge(mtr[2*node], mtr[2*node+1], mtr[node]);
		cay[node].resi(mtr[node].size()-1);
	}
}
void mupdate(int node, int l, int r, int p, int x){
	if(l==r){
		int it = lower_bound(mtr[node].begin()+1, mtr[node].end(), a[p], greater<int>())-mtr[node].begin();
		cay[node].update(it, x);
	}else{
		int mid = (l+r)/2;
		if(p<=mid){
			mupdate(2*node, l, mid, p, x);
		}else mupdate(2*node+1, mid+1, r, p, x);
		int it = lower_bound(mtr[node].begin()+1, mtr[node].end(), a[p], greater<int>())-mtr[node].begin();
		cay[node].update(it, x);
	}
}

int mquery(int node, int start, int end, int l, int r, int k){
	if(start > r or end < l){
		return 0;
	}
	if(l<=start and end<=r){
		int it = lower_bound(mtr[node].begin()+1, mtr[node].end(), k, greater<int>())-mtr[node].begin();
		// cout << start << ' ' << end << ' ' << k << '\n';
		it--;
		return cay[node].query(it);
	}
	int mid = (start+end)/2;
	int left = mquery(2*node, start, mid, l, r, k);
	int right = mquery(2*node+1, mid+1, end, l, r, k);
	return max(left, right);
}
int tv[300005];
vector<int> pos[300005];
int range[300005];
signed main(){
	int n, d;
	cin >> n >> d;
	map<int, int> mp;
	for (int i = 1;i<=n;++i){
		cin >> a[i];
		mp[a[i]] = -1;
	}
	int nen = 1;
	for (auto &i:mp){
		i.s = nen++;
	}
	for (int i = 1;i<=n;++i){
		a[i] = mp[a[i]];
		pos[a[i]].push_back(i);
		tv[i] = i;
	}
	sort(tv+1, tv+n+1, [](int p, int q){
		return a[p] > a[q];
	});
	nen--;
	build(1, 1, n);
	int tro = nen;
	int ll = 1, rr = 1;
	while(ll<=n){
		while(rr<=n and a[tv[ll]]==a[tv[rr]]){
			rr++;
		}
		for (int i = ll;i<rr;++i){
			int p = tv[i];
			int l = p, r = n;
			int sol = p;
			while(l<=r){
				int mid = (l+r)/2;
				Node c = query(1, 1, n, p, mid);
				if(c.best<d){
					l = mid+1;
					sol = mid;
				}else r = mid-1;
			}
			int cuoi = sol;
			if(sol!=n){
				cuoi++;
			}
			cuoi = min(n, cuoi);
			range[p] = cuoi;
		}
		int p = tv[ll];
		while(tro>=a[p]){
			for (int j:pos[tro]){
				update(1, 1, n, j);
			}
			tro--;
		}
		ll = rr;
	}
	for (int i= 1;i<=n;++i){
		// cout << range[i] << ' ';
	}
	// cout << '\n';
	mbuild(1, 1, n);
	mupdate(1, 1, n, n, 1);
	int res = 1;
	for (int i = n-1;i>=1;--i){
		 int sol = mquery(1, 1, n, i, range[i], a[i]);
		// cout << sol << '\n';
		mupdate(1, 1, n, i, sol+1);
		res = max(res, sol+1);
		sol = mquery(1, 1, n, i, range[i], a[i]-1);
		mupdate(1, 1, n, i, sol);
	}
	cout << res;
}

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