Submission #531184

#	Time	Username	Problem	Language	Result	Execution time	Memory
531184		chaoyue	Financial Report (JOI21_financial)	C++17	100 / 100	575 ms	37224 KiB

Main

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

#define ll long long

struct node{
	int s, e, m, maxi;
	node *l, *r;
	
	node(int S, int E){
		s = S;
		e = E;
		m = (s+e)/2;
		maxi = 0;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	
	int query(int S, int E){
		if(s > E || e < S) return 0;
		if(s >= S && e <= E) return maxi;
		return max(l->query(S, E), r->query(S, E));
	}
	
	void update(int idx, int V){
		if(s > idx || e < idx) return;
		if(s == idx && e == idx){
			maxi = V;
			return;
		}
		l->update(idx, V);
		r->update(idx, V);
		maxi = max(l->maxi, r->maxi);
	}
} *root;

bool cmp(pair<int, int> a, pair<int, int> b){
	if(a.first < b.first || (a.first == b.first && a.second > b.second)) return 1;
	return 0;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, d, l, r, pos;
	cin>>n>>d;
	vector<pair<int, int> > v(n);
	set<pair<int, int> > s;
	set<pair<int, int> >::iterator it;
	for(int i=0; i<n; i++){
		cin>>v[i].first;
		v[i].second = i;
	}
	sort(v.begin(), v.end(), cmp);
	/*for(int i=0; i<n; i++){
		cout<<"("<<v[i].first<<", "<<v[i].second<<") ";
	}
	cout<<"\n";*/
	s.insert({0, n-1});
	root = new node(0, n);
	for(int i=0; i<n; i++){
		//insert into s and find rightmost gap
		pos = v[i].second;
		if(!s.empty()){
			it = s.upper_bound({pos, n+1});
			if(it != s.begin()){
				it--;
				l = (*it).first;
				r = (*it).second;
				if(r >= pos){
					s.erase(it);
					if(pos - l >= d){
						s.insert({l, pos-1});
					}
					if(r - pos >= d){
						s.insert({pos+1, r});
					}
				}
			}
		}
		it = s.upper_bound({pos, n+1});
		if(it == s.begin()){
			l = 0;
		}
		else{
			it--;
			l = (*it).second + 1;
		}
		//cout<<"l: "<<l<<"\n";
		//cout<<"query: "<<root->query(l, pos)<<"\n";
		root->update(pos, root->query(l, pos) + 1);
		/*cout<<"updated: "<<root->query(pos, pos)<<"\nset: ";
		for(it = s.begin(); it!=s.end(); it++){
			cout<<"("<<(*it).first<<", "<<(*it).second<<") ";
		}
		cout<<"\n";*/
		
	}
	cout<<root->query(0, n-1);
	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