oj.uz

Submission #1096708

# Submission time Handle Problem Language Result Execution time Memory
1096708 2024-10-05T03:07:38 Z MinhTri2k8 Global Warming (CEOI18_glo) C++14
10 / 100
 2000 ms 6684 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second;
int n,t[1200010],x,a[200010],b[200010];
void update(int id, int l, int r, int u,int val)
{
    if (u<l || r<u) return;
    if (l==r)
    {
        t[id]=val;
        return;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,u,val);
    update(id*2+1,mid+1,r,u,val);
    t[id]=max(t[id*2],t[id*2+1]);
}
int get(int id, int l, int r, int u, int v)
{
    if (v<l || r<u) return 0;
    if (u<=l && r<=v) return t[id];
    int mid=(l+r)/2;
    return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
void solve1()
{
    int res=0;
    for (int i=1;i<=n;i++) b[i]=a[i];
    sort(b+1,b+1+n);
    for (int i=1;i<=n;i++)
    {
        a[i]=lower_bound(b+1,b+1+n,a[i])-b;
//        cout<<a[i]<<' ';
        a[i]++;
//        cout<<a[i]<<' ';
    }
    for (int i=1;i<=n;i++)
    {
        int tam=get(1,1,300000,1,a[i]-1);
        update(1,1,300000,a[i],tam+1);
        res=max(res,tam+1);
    }
    //cout<<get(1,1,300000,1,a[8])<<' ';
    cout<<res;
}
void solve2()
{
    int res=0;
    int c[200010];
    for (int j=1;j<=n;j++)
    {
        for (int i=0;i<=4*10000;i++) t[i]=0;
        for (int i=1;i<=n;i++) b[i]=a[i];
        for (int i=1;i<=n;i++) c[i]=a[i];
        for (int i=j+1;i<=n;i++) c[i]=a[i]+x,b[i]=a[i]+x;
//        for (int i=1;i<=n;i++) cout<<b[i]<<' ';

        sort(b+1,b+1+n);
        for (int i=1;i<=n;i++)
        {
            c[i]=lower_bound(b+1,b+1+n,c[i])-b;
//        cout<<a[i]<<' ';
            c[i]++;
//        cout<<a[i]<<' ';
        }
//        for (int i=1;i<=n;i++) cout<<c[i]<<' ';cout<<'\n';
        for (int i=1;i<=n;i++)
        {
            int tam=get(1,1,40000,1,c[i]-1);
            update(1,1,40000,c[i],tam+1);
//            cout<<tam<<' ';
            res=max(res,tam+1);
        }
        //cout<<get(1,1,300000,1,a[8])<<' ';
//        cout<<res<<'\n';
    }
    cout<<res;
}
int main()
{
    //freopen("daydep.inp","r",stdin);
    //freopen("daydep.out","w",stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>x;
    for (int i=1;i<=n;i++) cin>>a[i];
    if (x==0) solve1();
    else solve2();
return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 6684 KB Output is correct
2 Correct 113 ms 6512 KB Output is correct
3 Correct 111 ms 6480 KB Output is correct
4 Correct 109 ms 6484 KB Output is correct
5 Correct 67 ms 4432 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2031 ms 2544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2051 ms 3412 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -