Submission #530855

#	Time	Username	Problem	Language	Result	Execution time	Memory
530855		chaoyue	Financial Report (JOI21_financial)	C++17	0 / 100	4070 ms	37900 KiB

Main

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

#define ll long long

struct node{
	int s, e, m, idx, val, lazyidx;
	bool removed;
	node *l, *r;
	
	node(int S, int E){
		s = S;
		e = E;
		m = (s+e)/2;
		idx = INT_MAX;
		if(s == 0){
			val = -1;
		}
		else{
			val = INT_MAX;
		}
		removed = 0;
		lazyidx = 0;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	
	void propagate(){
		if(removed){
			idx = INT_MAX;
			val = INT_MAX;
			if(s != e){
				l->removed = 1;
				r->removed = 1;
			}
			removed = 0;
		}
		if(lazyidx){
			idx = lazyidx;
			if(s != e){
				l->lazyidx = lazyidx;
				r->lazyidx = lazyidx;
			}
			lazyidx = 0;
		}
	}
	
	void remove(int lim){  //might take O(n^2), maybe need introduce minidx
		propagate();
		if(idx < lim){
			removed = 1;
			propagate();
			return;
		}
		if(s != e){
			l->remove(lim);
			r->remove(lim);
			idx = max(l->idx, r->idx);
			val = min(l->val, r->val);
		}
	}
	
	void setidx(int i, int x){
		propagate();
		if(val > x){
			lazyidx = i;
			propagate();
			return;
		}
		if(s != e){
			l->setidx(i, x);
			r->setidx(i, x);
			idx = max(l->idx, r->idx);
		}
	}
	
	void extend(int pos, int i, int x){
		propagate();
		if(s > pos || e < pos) return;
		if(s == pos && e == pos){
			val = x;
			idx = i;
		}
		if(s != e){
			l->extend(pos, i, x);
			r->extend(pos, i, x);
			idx = max(l->idx, r->idx);
			val = min(l->val, r->val);
		}
	}
	
	pair<int, int> walk(int x){
		propagate();
		if(s == e) return {s, val};
		if(r->val < x) return r->walk(x);
		return l->walk(x);
	}
	
} *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);
	for(int i=0; i<n; i++){
		cin>>x;
		root->remove(i-d);
		data = root->walk(x); //{idx, val}
		root->extend(data.first + 1, i, x);
		root->setidx(i, x);
	}
	data = root->walk(INT_MAX-1);
	cout<<data.first;
	return 0;
}

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