Submission #465641

#	Time	Username	Problem	Language	Result	Execution time	Memory
465641		mariowong	Financial Report (JOI21_financial)	C++14	100 / 100	532 ms	25816 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;

int n,d,ct,a[300005],seg[1200005],ans,now,indx[300005],nw[300005];
deque <int> dq;
vector <pair<int,int>  > v; 
priority_queue <pair<int,int>  > pq,del,mn;
void update(int id,int l,int r,int pos,int v){
	if (l == r)
	seg[id]=v;
	else
	{
		int mid=(l+r)/2;
		if (pos <= mid) update(id*2,l,mid,pos,v);
		else update(id*2+1,mid+1,r,pos,v);	
		seg[id]=max(seg[id*2],seg[id*2+1]);
	}
}
int query(int id,int l,int r,int x,int y){
	if (x <= l && y >= r)
	return seg[id];
	if (l > y || r < x)
	return -1;
	int mid=(l+r)/2;
	return max(query(id*2,l,mid,x,y),query(id*2+1,mid+1,r,x,y));
}
void debug(int id,int l,int r){
	cerr << seg[id] << " " << l << " " << r << "\n";
	if (l != r){
		int mid=(l+r)/2;
		debug(id*2,l,mid);
		debug(id*2+1,mid+1,r);	
	}
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> d;
	for (int i=1;i<=n;i++){
		cin >> a[i];
		indx[i]=n+1;
		v.push_back(make_pair(a[i],i));
	}
	sort(v.begin(),v.end());
	for (int i=0;i<n;i++){
		if (i == 0 || v[i].first != v[i-1].first) ct++;
		a[v[i].second]=ct;
	}
	for (int i=1;i<=n;i++){
		mn.push(make_pair(-a[i],i));
		while (!mn.empty() && i-mn.top().second >= d){
			mn.pop();
		}
		while (!del.empty() && -del.top().first < -mn.top().first){
			indx[del.top().second]=i+1;
			del.pop();
		}
		if (i >= d)
		del.push(make_pair(-a[i-d+1],i-d+1));
	}
/*	for (int i=1;i<=n;i++){
		cerr << a[i] << " ";
	}
	cerr << "\n";
	for (int i=1;i<=n;i++){
		cerr << indx[i] << " ";
	}
	cerr << "\n";*/
	for (int i=1;i<=n;i++){
		while (!pq.empty() && -pq.top().first == i){
			if (-pq.top().first == nw[pq.top().second])
			update(1,0,ct,pq.top().second,0);
			pq.pop(); 
		}
	//	if (i == 8)
	//	debug(1,0,ct);
	//	if (i == 8)
	//	cerr << query(1,0,ct,a[i],a[i]) << " " << query(1,0,ct,0,4) << "\n";
		now=max(query(1,0,ct,a[i],a[i]),query(1,0,ct,0,a[i]-1)+1);
		update(1,0,ct,a[i],now);
	//	cerr <<i <<  " --- " << now << "\n";
		ans=max(ans,now);
		pq.push(make_pair(-indx[i],a[i]));
		nw[a[i]]=indx[i];
	//	cout << a[i] << " " << i << " " << now << "\n";
	}
	cout << ans << "\n";
	return 0;
}

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