oj.uz

Submission #483317

# Submission time Handle Problem Language Result Execution time Memory
483317 2021-10-28T16:57:52 Z MOUF_MAHMALAT Global Warming (CEOI18_glo) C++14
100 / 100
 1170 ms 191804 KB 
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define F first
#define S second
using namespace std;
typedef int ll;
const ll ee=1e9;
struct node
{
    node*l=0,*r=0;
    ll val=0;
} *lis,*lds;
ll n,k,a[200009],ans;
map<ll,vector<ll> >v;
ll best_lis(node*d,ll l,ll r,ll x)
{
    if(l>x||d==0)
        return 0;
    if(r<=x)
        return d->val;
    ll m=(l+r)/2;
    return max(best_lis(d->l,l,m,x),best_lis(d->r,m+1,r,x));
}
ll best_lds(node*d,ll l,ll r,ll x)
{
    if(r<x||d==0)
        return 0;
    if(l>=x)
        return d->val;
    ll m=(l+r)/2;
    return max(best_lds(d->l,l,m,x),best_lds(d->r,m+1,r,x));
}
void up_lis(node*d,ll l,ll r,ll id)
{
    if(l==r)
    {
        if(v[l].empty())
            d->val=0;
        else
            d->val=v[l].back();
        return;
    }
    ll m=(l+r)/2;
    if(id<=m)
    {
        if(d->l==0)
            d->l=new node;
        up_lis(d->l,l,m,id);
    }
    else
    {
        if(d->r==0)
            d->r=new node;
        up_lis(d->r,m+1,r,id);
    }
    d->val=0;
    if(d->l!=0)
        d->val=d->l->val;
    if(d->r!=0)
        d->val=max(d->val,d->r->val);
}
void up_lds(node*d,ll l,ll r,ll id,ll x)
{
    if(l==r)
        return void(d->val=x);
    ll m=(l+r)/2;
    if(id<=m)
    {
        if(d->l==0)
            d->l=new node;
        up_lds(d->l,l,m,id,x);
    }
    else
    {
        if(d->r==0)
            d->r=new node;
        up_lds(d->r,m+1,r,id,x);
    }
    d->val=0;
    if(d->l!=0)
        d->val=d->l->val;
    if(d->r!=0)
        d->val=max(d->val,d->r->val);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    lis=new node;
    lds=new node;
    cin>>n>>k;
    for(ll i=1; i<=n; i++)
    {
        cin>>a[i];
        ll op=best_lis(lis,0,ee,a[i]-1)+1;
        v[a[i]].push_back(op);
        up_lis(lis,0,ee,a[i]);
    }
    for(ll i=n; i; i--)
    {
        v[a[i]].pop_back();
        up_lis(lis,0,ee,a[i]);
        ll op=best_lds(lds,0,ee,a[i]+1)+1;
        up_lds(lds,0,ee,a[i],op);
        op+=best_lis(lis,0,ee,a[i]+k-1);
        ans=max(ans,op);
    }
    cout<<ans;
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
13.0 / 13.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1159 ms 191020 KB Output is correct
2 Correct 1159 ms 190888 KB Output is correct
3 Correct 1147 ms 190860 KB Output is correct
4 Correct 1157 ms 190916 KB Output is correct
5 Correct 420 ms 102628 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 54200 KB Output is correct
2 Correct 240 ms 54568 KB Output is correct
3 Correct 233 ms 54684 KB Output is correct
4 Correct 110 ms 29212 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 82 ms 8200 KB Output is correct
7 Correct 159 ms 40716 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 102036 KB Output is correct
2 Correct 491 ms 102676 KB Output is correct
3 Correct 1081 ms 191804 KB Output is correct
4 Correct 388 ms 103532 KB Output is correct
5 Correct 173 ms 24752 KB Output is correct
6 Correct 303 ms 46532 KB Output is correct
7 Correct 312 ms 46536 KB Output is correct
8 Correct 313 ms 76868 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 320 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 4 ms 1740 KB Output is correct
20 Correct 3 ms 1740 KB Output is correct
21 Correct 4 ms 1744 KB Output is correct
22 Correct 4 ms 1740 KB Output is correct
23 Correct 3 ms 972 KB Output is correct
24 Correct 2 ms 972 KB Output is correct
25 Correct 2 ms 460 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 1159 ms 191020 KB Output is correct
28 Correct 1159 ms 190888 KB Output is correct
29 Correct 1147 ms 190860 KB Output is correct
30 Correct 1157 ms 190916 KB Output is correct
31 Correct 420 ms 102628 KB Output is correct
32 Correct 232 ms 54200 KB Output is correct
33 Correct 240 ms 54568 KB Output is correct
34 Correct 233 ms 54684 KB Output is correct
35 Correct 110 ms 29212 KB Output is correct
36 Correct 1 ms 332 KB Output is correct
37 Correct 82 ms 8200 KB Output is correct
38 Correct 159 ms 40716 KB Output is correct
39 Correct 485 ms 102036 KB Output is correct
40 Correct 491 ms 102676 KB Output is correct
41 Correct 1081 ms 191804 KB Output is correct
42 Correct 388 ms 103532 KB Output is correct
43 Correct 173 ms 24752 KB Output is correct
44 Correct 303 ms 46532 KB Output is correct
45 Correct 312 ms 46536 KB Output is correct
46 Correct 313 ms 76868 KB Output is correct
47 Correct 504 ms 102680 KB Output is correct
48 Correct 498 ms 102724 KB Output is correct
49 Correct 1170 ms 191780 KB Output is correct
50 Correct 438 ms 103572 KB Output is correct
51 Correct 264 ms 25308 KB Output is correct
52 Correct 453 ms 49000 KB Output is correct
53 Correct 334 ms 48948 KB Output is correct
54 Correct 383 ms 48840 KB Output is correct
55 Correct 791 ms 144240 KB Output is correct