Submission #530862

#	Time	Username	Problem	Language	Result	Execution time	Memory
530862		chaoyue	Financial Report (JOI21_financial)	C++17	60 / 100	4051 ms	41004 KiB

Main

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

#define ll long long

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

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