Submission #533832

#	Time	Username	Problem	Language	Result	Execution time	Memory
533832		penguin133	Financial Report (JOI21_financial)	C++14	100 / 100	580 ms	37252 KiB

Main

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

set<pair<int, int> > s;
set<pair<int, int> > :: iterator it;
pair<int, int> A[300005];
bool cmp(pair<int, int> a, pair<int, int> b){
	if(a.first != b.first)return a.first < b.first;
	else return a.second > b.second;
}
int n,d;
struct node{
	int s,e,m,val, lazy;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)/2;
		val = 0;
		if(s != e)l = new node(s, m) , r=  new node(m+ 1, e);
	}
	void update(int p, int v){
		if(s == e)val = v;
		else{
			if(p <= m)l->update(p,v);
			else r->update(p,v);
			val = max(l->val, r->val);
		}
	}
	int query(int a, int b){
		if(s == a && b == e)return val;
		else if(b <= m)return l->query(a,b);
		else if(a > m)return r->query(a,b);
		else return max(l->query(a,m), r->query(m+1, b));
	}
}*root;
int main(){
	cin >> n >> d;
	root= new node(1, n);
	if(d < n - 1)s.insert({1,n});
	s.insert({0,0});
	for(int i=1;i<=n;i++)cin >> A[i].first, A[i].second = i;
	sort(A+1, A+1+n, cmp);
	for(int i=1;i<=n;i++){
		int x = A[i].second;
		it = s.upper_bound({x, 1e9});
		if(it != s.begin()){
			it--;
			if(it->first <= x && it->second >= x){
				int tmp = it->first, tmp2 = it->second;
				s.erase(it);
				if(x-tmp >= d)s.insert({tmp,x-1});
				if(tmp2-x>= d)s.insert({x+1,tmp2});
			}
		}
		int ans =0 ;
		it = s.upper_bound({x, 1e9});
		if(it != s.begin()){
			it--;
			//cout << i << " " << x << " " << it->second<< '\n';
			ans = root->query(it->second + 1, x);
		}
		ans++;
		root->update(x,ans);
		
	}
	cout << root->val;
}

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