oj.uz

답안 #1096675

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1096675 2024-10-05T01:47:07 Z Wewoo Global Warming (CEOI18_glo) C++17
37 / 100
 222 ms 21732 KB 
#include <bits/stdc++.h>

using namespace std;

const int N=(int) 2e5+9;

unordered_map <long long , long long > nen;

long long a[N],f[N],temp[N],f2[N];
long long st[4*N];
long long res,dp;
int n,x,idx,t;

void up(int id, int l, int r, int vt, int val) {

    if (l>vt || r<vt) return;

    if (l==r ) {
        st[id]=val;
        return;
    }

//    if (vt==2)
//    cout<<l<<" "<<r<<endl;
    int m=(l+r)/2;

    up(id*2,l,m,vt,val);
    up(id*2+1,m+1,r,vt,val);

    st[id]=max(st[id*2],st[id*2+1]);

}

long long get(int id, int l, int r, int u, int v) {
    if (l>v || r <u) return (int) -1e12;

    if (u<=l && r<=v) return st[id];

    int m=(l+r)/2;

    long long get1=get(id*2,l,m,u,v);
    long long get2=get(id*2+1,m+1,r,u,v);

//    if (u==2) {
//        cout<<l<<" "<<r<<endl;
//        cout<<get1<<" "<<get2<<endl;
//        cout<<endl;
//    }

    return max(get1,get2);
}

int small(int l, int r,long long x) {
    int vt=r;

    while (l<=r) {
        int m=(l+r)/2;
        if (temp[m]<=x) vt=m,r=m-1;
        else l=m+1;
    }

    return vt;
}

void solve() {
    res=idx;
    int pos=nen[a[n]];
    up(1,1,t,pos,f2[n]);


    for (int i=n-1; i>=1; i--) {
        int vt=upper_bound(temp+1,temp+1+n,a[i]-x)-temp;
        int pos=nen[temp[vt]];
        dp=get(1,1,t,pos,t);
        res=max(res,dp+f[i]);
        pos=nen[a[i]];
        up(1,1,t,pos,f2[i]);
    }

    cout<<res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

   // freopen("daydep.inp","r",stdin);
    //freopen("daydep.out","w",stdout);

    cin>>n>>x;

    for (int i=1; i<=n; i++)
        cin>>a[i];

    for (int i=1; i<=n; i++) {
        temp[idx+1]=(int) 1e12;
        int pos=lower_bound(temp+1,temp+idx+1,a[i])-temp;
        temp[pos]=a[i];
        idx=max(idx,pos);
        f[i]=pos;
    }

    for (int i=1; i<=n; i++) temp[i]=0;
    idx=0;

    for (int i=n; i>=1; i--) {
        temp[idx+1]=(int) -1e12;
        int pos=small(1,idx+1,a[i]);
        temp[pos]=a[i];
        idx=max(idx,pos);
        f2[i]=pos;
    }

    for (int i=1; i<=n; i++)
        temp[i]=a[i];

    sort(temp+1,temp+1+n);

    for (int i=1; i<=n; i++) {
        if (temp[i]!=temp[i-1]) t++;
        nen[temp[i]]=t;
    }

    solve();
    return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 222 ms 21732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 5736 KB Output is correct
2 Correct 38 ms 5740 KB Output is correct
3 Correct 39 ms 5612 KB Output is correct
4 Correct 17 ms 3768 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 18 ms 3888 KB Output is correct
7 Correct 33 ms 5740 KB Output is correct

Subtask #6
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 10952 KB Output is correct
2 Correct 58 ms 10948 KB Output is correct
3 Correct 134 ms 21628 KB Output is correct
4 Correct 71 ms 14272 KB Output is correct
5 Correct 30 ms 10692 KB Output is correct
6 Correct 55 ms 20348 KB Output is correct
7 Correct 69 ms 20856 KB Output is correct
8 Correct 51 ms 10960 KB Output is correct

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -