Submission #530634

#	Time	Username	Problem	Language	Result	Execution time	Memory
530634		chaoyue	Financial Report (JOI21_financial)	C++17	19 / 100	279 ms	43408 KiB

Main

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

#define ll long long

struct node{
	int s, e, m, mini, tail, lazytail;
	bool removed;
	node *l, *r;
	
	node(int S, int E){
		s = S;
		e = E;
		m = (s+e)/2;
		if(s == 0){
			mini = -1;
		}
		else{
			mini = INT_MAX;
		}
		tail = -1;
		removed = 0;
		lazytail = 0;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	
	void propagate(){
		if(removed){
			removed = 0;
			mini = INT_MAX;
			tail = INT_MIN;
			if(s != e){
				l->removed = 1;
				r->removed = 1;
			}
		}
		if(lazytail){
			tail += lazytail;
			if(s != e){
				l->lazytail += lazytail;
				r->lazytail += lazytail;
			}
			lazytail = 0;
		}
	}
	
	void addtail(int S){
		propagate();
		if(e < S) return;
		if(s >= S){
			lazytail++;
			return;
		}
		l->addtail(S);
		r->addtail(S);
	}
	
	void remove(int E){
		propagate();
		if(s > E) return;
		if(s && e <= E){
			removed = 1;
			return;
		}
		if(s != e){
			l->remove(E);
			r->remove(E);
		}
	}
	
	void updatemini(int idx, int val, int newtail){
		propagate();
		if(s > idx || e < idx) return;
		if(s == idx && e == idx){
			mini = val;
			tail = newtail;
			return;
		}
		l->updatemini(idx, val, newtail);
		r->updatemini(idx, val, newtail);
		mini = min(l->mini, r->mini);
	}
	
	pair<int, int> walk(int val){
		propagate();
		if(s == e) return {s, tail};
		if(r->mini < val) return r->walk(val);
		return l->walk(val);
	}
	
	//range update tail from x-end, tail += 1
	//range update mini from 1-x, set mini = INT_MAX
	//range update tail from 1-x, set tail = INT_MIN
	//point update mini at x, set mini = val
	//binary search for position of min val
} *root;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, d, x;
	pair<int, int> data;
	cin>>n>>d;
	root = new node(0, n);
	vector<pair<int, int> > v(n, {0, 0});
	for(int i=0; i<n; i++){
		cin>>x;
		data = root->walk(x);  //{idx, tail}
		if(i - data.second > d){
			//need to invalidate idx and all below it
			root->remove(data.first);
			root->updatemini(1, x, i-1);
			root->addtail(1);
		}
		else{
			root->updatemini(data.first + 1, x, i-1);
			root->addtail(data.first + 1);
		}
	}
	data = root->walk(INT_MAX-1);
	cout<<data.first;
	return 0;
}

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