제출 #530644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
530644		chaoyue	Financial Report (JOI21_financial)	C++17	31 / 100	271 ms	39196 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;
			propagate();
			return;
		}
		if(s != e){
			l->remove(E);
			r->remove(E);
			mini = min(l->mini, r->mini);
		}
		//last case: s==e==0 do nothing
	}
	
	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<int> a(n);
	for(int i=0; i<n; i++){
		cin>>a[i];
	}
	for(int i=0; i<n; i++){
		x = a[i];
		data = root->walk(x);  //{idx, tail}
		if(data.first && i - data.second > d){
			root->updatemini(data.first, INT_MAX, INT_MIN);
			i--;
		}
		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: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35