Submission #535836

#	Time	Username	Problem	Language	Result	Execution time	Memory
535836		radal	Financial Report (JOI21_financial)	C++17	100 / 100	572 ms	29808 KiB

Main

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
constexpr ll N = 3e5+20,mod = 1e9+7,inf = 1e9+10,maxm = 1e6;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    }
    return z;
}
int a[N],par[N],seg[N*4],dp[N];
int n,d;
void upd(int l,int r,int p,int x,int v = 1){
    if (r-l == 1){
        seg[v] = x;
        return;
    }
    int m = (l+r) >> 1,u = (v << 1);
    if (p < m) upd(l,m,p,x,u);
    else upd(m,r,p,x,u|1);
    seg[v] = max(seg[u],seg[u|1]);
}
int que(int l,int r,int s,int e,int v = 1){
    if (s <= l && r <= e) return seg[v];
    if (s >= r || l >= e || s >= e) return 0;
    int m = (l+r) >> 1,u = (v << 1);
    return max(que(l,m,s,e,u),que(m,r,s,e,u|1));
}
int getpar(int v){
    if (v == par[v]) return v;
    return par[v] = getpar(par[v]);
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> d;
    vector<pll> ve;
    rep(i,0,n){
        cin >> a[i];
        par[i] = i;
        ve.pb({a[i],-i});
    }
    sort(ve.begin(),ve.end());
    set<int> st;
    int ans = 0;
    rep(k,0,n){
        int i = -ve[k].Y;
        if (st.empty()){
            dp[i] = 1;
            ans = max(ans,1);
            st.insert(i);
            upd(0,n,i,1);
            continue;
        }
        if (i < *(st.begin())){
            int j = *(st.begin());
            dp[i] = 1;
            ans = max(ans,1);
            st.insert(i);
            if (j-i <= d) par[j] = i;
            upd(0,n,i,1);
            continue;
        }
        auto it = st.lower_bound(i);
        it--;
        int j = (*it);
        if (i-j <= d) par[i] = getpar(j);
        dp[i] = 1+que(0,n,par[i],i);
        ans = max(ans,dp[i]);
        it++;
        if (it != st.end())
            if((*it)-i <= d)
                par[(*it)] = i;
        upd(0,n,i,dp[i]);
        st.insert(i);
    }
    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