oj.uz

Submission #260509

# Submission time Handle Problem Language Result Execution time Memory
260509 2020-08-10T12:24:45 Z stefantaga Global Warming (CEOI18_glo) C++14
28 / 100
 2000 ms 3448 KB 
#include <bits/stdc++.h>

using namespace std;
int n,x,i,v[200005],b[200005],poz,lcresc[200005],ldesc[200005],j,maxim;
int caut (int val)
{
    int st=1,dr=n,mij,sol=0;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (b[mij]<val)
        {
            sol=mij;
            st=mij+1;
        }
        else
        {
            dr=mij-1;
        }
    }
    return sol;
}
int caut1 (int val)
{
    int st=1,dr=n,mij,sol=0;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (b[mij]<=val)
        {
            sol=mij;
            st=mij+1;
        }
        else
        {
            dr=mij-1;
        }
    }
    return sol;
}
int main()
{
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>x;
    for (i=1;i<=n;i++)
    {
        b[i]=2000000005;
    }
    for (i=1;i<=n;i++)
    {
        cin>>v[i];
        poz=caut(v[i]);
        if (v[i]<b[poz+1])
        {
            b[poz+1]=v[i];
            lcresc[i]=poz+1;
        }
    }
    for (i=1;i<=n;i++)
    {
        b[i]=-2000000005;
    }
    for (i=n;i>=1;i--)
    {
        poz=caut1(v[i]);
        if (v[i]>b[poz])
        {
            b[poz]=v[i];
            ldesc[i]=n-poz+1;
        }
    }
    maxim=1;
    for (i=1;i<=n;i++)
    {
        for (j=i-1;j>=1;j--)
        {
             if (v[j]-x<v[i])
             {
                 maxim=max(maxim,ldesc[i]+lcresc[j]);
             }
        }
    }
    cout<<maxim<<'\n';
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2093 ms 1144 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 2099 ms 1912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Execution timed out 2029 ms 3448 KB Time limit exceeded
28 Halted 0 ms 0 KB -