Submission #425111

#	Time	Username	Problem	Language	Result	Execution time	Memory
425111		CSQ31	Financial Report (JOI21_financial)	C++14	100 / 100	1066 ms	72704 KiB

Main

#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN = 3e5+55;
vector<int>par(MAXN),rg(MAXN);
vector<multiset<int>>has(MAXN);
int n,d;
int find(int x){
	if(par[x] == x)return x;
	else return par[x] = find(par[x]);
}
multiset<int>cur;
void add(int x){
	cur.insert(x);
	auto p = cur.ub(x);
	if(p != cur.end() && *p - x <=d)par[x] = *p;
	else par[x] = x;
	p = cur.lb(x);
	if(p != cur.begin()){
		p--;
		if(x - *p <= d){
			par[*p] = x;
		}
	}
}
vector<int>t(4*MAXN,-1e9);
void update(int v,int l,int r,int pos){
	if(l == r){
		if(has[pos].empty())t[v] = -1e9;
		else {
			auto it = has[pos].end();
			it--;
			t[v] = *it;
		}
		return;
	}
	int tm = (l+r)/2;
	if(pos<=tm)update(2*v,l,tm,pos);
	else update(2*v+1,tm+1,r,pos);
	t[v] = max(t[2*v],t[2*v+1]);
}
int query(int v,int l,int r,int tl,int tr){
	if(l > r)return -1e9;
	if(l == tl && r == tr){
		return t[v];
	}
	int tm = (tl+tr)/2;
	return max(query(2*v,l,min(r,tm),tl,tm),query(2*v+1,max(l,tm+1),r,tm+1,tr));
}
int main()
{
	owo
	cin>>n>>d;
	vector<int>a(n),crd;
	for(int i=0;i<n;i++){
		cin>>a[i];
		crd.pb(a[i]);
	}
	sort(all(crd));
	crd.resize(unique(all(crd)) - crd.begin());
	for(int i=0;i<n;i++)a[i] = lb(all(crd),a[i]) - crd.begin()+1;
	vector<pii>b;
	for(int i=0;i<n;i++)b.pb({a[i],i});
	sort(all(b));
	for(int i=0;i<n;){
		int j = i;
		while(j<n && b[j].fi ==b[i].fi){
			add(b[j].se);
			j++;
		}  
		while(i<j){
			rg[b[i].se] = find(b[i].se)+d-1;
			i++;
		}
	}
	/*
	for(int i=0;i<n;i++)cout<<a[i]<<" ";
	cout<<'\n';
	for(int i=0;i<n;i++)cout<<rg[i]<<" ";
	cout<<'\n';*/
	multiset<pii>can;
	int ans = 0,m = sz(crd);
	if(n==1)ans=1;
	vector<int>dp(n);
	for(int i=0;i<n;i++){
		if(can.empty()){
			dp[i] = 1;
		}else{
			while(!can.empty()){
				auto it = can.ub(make_pair(i-1,-1));
				if(it == can.begin())break;
				it--;
				if(it->fi <= i-1){
					int idx = it->se;
					has[a[idx]].erase(dp[idx]);
					can.erase(it);
					update(1,1,m,a[idx]);
				}
				else break;
			}
			if(a[i] == 1)dp[i] = 1;
			else dp[i] = query(1,1,a[i]-1,1,m) + 1;
			dp[i] = max(dp[i],query(1,a[i],a[i],1,m));
			dp[i] = max(dp[i],1);
		}
	    has[a[i]].insert(dp[i]);
		can.insert({rg[i],i});
		update(1,1,m,a[i]);
		ans = max(ans,dp[i]);
	}
	cout<<ans<<'\n';
}

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