Submission #1180286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180286		Alish	Financial Report (JOI21_financial)	C++20	0 / 100	562 ms	33868 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;
typedef long double     ld;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp              make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("input19.txt" , "r" , stdin) ;

const int N = 3e5+23;
int n;
ll a[N];
int seg[4*N], lpz[4*N];
int segg[4*N];
int d;

void Shift(int l, int r, int ind){
    if(r-l==1) return;
    if(!lpz[ind]) return;
    seg[2*ind+1]=max(seg[2*ind+1], lpz[ind]);
    lpz[2*ind+1]=max(seg[2*ind+1], lpz[ind]);

    seg[2*ind+2]=max(seg[2*ind+2], lpz[ind]);
    lpz[2*ind+2]=max(seg[2*ind+2], lpz[ind]);

    lpz[ind]=0;
}

void Set(int i, int x, int l=1, int r=n+1, int ind=0){
    Shift(l, r, ind);
    if(r-l==1){
        seg[ind]=x;
        return;
    }
    int mid=(r+l)>>1;
    if(i<mid) Set(i, x, l, mid, 2*ind+1);
    else Set(i, x, mid, r, 2*ind+2);
    seg[ind]=max(seg[2*ind+1], seg[2*ind+2]) ;
}

void upd(int lx, int rx, int x, int l=1, int r=n+1, int ind=0){
    Shift(l, r, ind);
    if(lx>=r || rx<=l) return;
    if(lx<=l && rx>=r){
        seg[ind]=max(seg[ind], x);
        lpz[ind]=max(lpz[ind], x);
        return;
    }
    int mid=(r+l)>>1;
    upd(lx, rx, x, l, mid, 2*ind+1);
    upd(lx, rx, x, mid, r, 2*ind+2);
    seg[ind]=max(seg[2*ind+1], seg[2*ind+2]);
}

int get(int i, int l=1, int r=n+1, int ind=0){
    Shift(l, r, ind);
    if(r-l==1)return seg[ind];
    int mid=(r+l)>>1;
    if(i<mid) return get(i, l, mid, 2*ind+1);
    return get(i, mid, r, 2*ind+2);
}

void updd(int i, int x, int l=1, int r=n+1, int ind=0){
    if(r-l==1) {
        segg[ind]=x;
        return;
    }
    int mid=(r+l)>>1;
    if(i<mid) updd(i, x, l, mid, 2*ind+1);
    else updd(i, x, mid, r, 2*ind+2);
    segg[ind]=max(segg[2*ind+1], segg[2*ind+2]);
}

int gettt(int lx, int rx, int l=1, int r=n+1, int ind=0){
    if(lx>=r || rx<=l) return n+1;
    if(segg[ind]<=d) return n+1;
    if(r-l==1) return l;
    int mid=(r+l)>>1;
    int r1=gettt(lx, rx, l, mid, 2*ind+1);
    if(r1==n+1) r1=gettt(lx, rx, mid, r, 2*ind+2);
    return r1;
}



int main()
{
    fast_io
    cin>>n>>d;
    vector<pll> vec;
    for (int i=1; i<=n; i++){
        cin>>a[i];
        vec.pb({a[i], -i});
    }
    sort(all(vec));
    set<int> st;
    for (int x=0; x<n; x++){
        int i=-vec[x].S;
        int pre=-n;
        int nxt=n+1;
        if(st.lower_bound(i)!=st.begin()){
            auto kir=st.lower_bound(i);
            kir--;
            pre=*kir;
        }
        if(st.upper_bound(i)!=st.end()) nxt=*st.upper_bound(i);

        int num=1;
        if(i-pre<=d) num=get(pre)+1;
        Set(i, num);
        updd(i, i-pre);
        if(nxt<=n) updd(nxt, nxt-i);

        upd(i, gettt(i+1, n+1), num);
        st.insert(i);
    }
    cout<<get(n)<<endl;


}

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