Submission #711213

#	Time	Username	Problem	Language	Result	Execution time	Memory
711213		Antekb	Financial Report (JOI21_financial)	C++17	100 / 100	709 ms	48992 KiB

Main

#include<bits/stdc++.h>

#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pp pop_back
#define all(x) (x).begin(), (x).end()

using namespace std;

void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
	cerr<<h;
	if(sizeof...(t))cerr<<", ";
	debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<pii>;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N=3e5+5;
int tab[N], zas[N];
vi todo[N+N];
int dp[N];
int val[N+N];
void ust(int v, int c){
	v+=N;
	val[v]=c;
	v/=2;
	for(;v; v>>=1){
		val[v]=max(val[v+v], val[v+v+1]);
	}
}
int get(int l, int r){
	int ans=0;
	for(l+=N, r+=N; l<r; l>>=1, r>>=1){
		if(l&1)ans=max(ans, val[l++]);
		if(r&1)ans=max(ans, val[--r]);
	}
	return ans;
}
int main(){
	//ios_base::sync_with_stdio(0);cin.tie(0);
	int n, d;
	cin>>n>>d;
	vii sca(n);
	for(int i=0; i<n; i++){
		cin>>sca[i].st;
		sca[i].nd=-i;
	}
	sort(all(sca));
	set<int> S, S2;
	S.insert(n+d);
	for(int i=0; i<n; i++){
		int j=-sca[i].nd;
		tab[j]=i;
		auto it=S.lower_bound(j);
		if(*it-j>d)S2.insert(j);
		if(it!=S.begin()){
			it--;
			if(S2.find(*it)!=S2.end())S2.erase(*it);
			if(j-(*it)>d)S2.insert(*it);
		}
		S.insert(j);
		it=S2.lower_bound(j);
		zas[j]=d+*it;
		todo[zas[j]].pb(j);
	}
	int ans=0;
	for(int i=0; i<n; i++){
		dp[i]=get(0, tab[i])+1;
		ust(tab[i], dp[i]);
		//deb(i, tab[i], dp[i], zas[i]);
		ans=max(ans, dp[i]);
		for(int j:todo[i])ust(tab[j], 0);
	}
	cout<<ans;
}

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