oj.uz

Submission #318037

# Submission time Handle Problem Language Result Execution time Memory
318037 2020-10-31T09:48:43 Z Dymo Global Warming (CEOI18_glo) C++14
0 / 100
 534 ms 10968 KB 
#include<bits/stdc++.h>

using namespace std;


#define pb    push_back
#define eb   emplace_back
#define ll  int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
const ll maxn=5e5+50;
const ll mod =998244353 ;
const ll base=3e18;
vector<ll> vt;

ll st[4][4*maxn];
ll a[maxn];

void update(ll id,ll left,ll right,ll x,ll diff,ll t )
{
    if (x>right||x<left) return ;
    if (right==left )
    {
        st[t][id]=max(st[t][id],diff);
        return ;
    }
    ll mid=(left+right)/2;
    update(id*2,left,mid, x, diff,t);
    update(id*2+1, mid+1, right, x, diff,t);
    st[t][id]=max(st[t][id*2],st[t][id*2+1]);
}
ll get(ll id,ll left,ll right,ll x,ll y,ll t)
{
    if (x>right||y<left||x> y) return 0;
    if (x<=left&&y>=right)
    {
        return st[t][id];
    }
    ll mid=(left+right)/2;
    return max(get(id*2,left,mid, x, y, t ),get(id*2+1, mid+1, right, x, y, t));

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n, x ;
    cin>> n>> x ;
    vt.pb(-1e15);
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        vt.pb(a[i]);
        vt.pb(a[i]-x);
    }
    sort(vt.begin(),vt.end());
    vt.resize(unique(vt.begin(),vt.end())-vt.begin());
    ll ans=0;
    for (int i=1;i<=n;i++)
    {
        ll h=lower_bound(vt.begin(),vt.end(),a[i])-vt.begin();
        ll t=get(1,1,vt.size()-1,1,h-1,0)+1;
        ll p=get(1,1,vt.size()-1,1,h-1,1)+1;
        update(1,1,vt.size(),h,t,0);
        update(1,1,vt.size(),h,p,1);
        ll h1=lower_bound(vt.begin(),vt.end(),a[i]-x)-vt.begin();
        update(1,1,vt.size(),h1,t,1);
        ans=max(ans,t);
         ans=max(ans,p);
    }
    cout <<ans<<endl;




}

Compilation message

glo.cpp:15:15: warning: overflow in conversion from 'double' to 'int' changes value from '3.0e+18' to '2147483647' [-Woverflow]
   15 | const ll base=3e18;
      |               ^~~~
glo.cpp: In function 'int main()':
glo.cpp:52:11: warning: overflow in conversion from 'double' to 'std::vector<int>::value_type' {aka 'int'} changes value from '-1.0e+15' to '-2147483648' [-Woverflow]
   52 |     vt.pb(-1e15);
      |           ^~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 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 364 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 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 9080 KB Output is correct
2 Correct 437 ms 8920 KB Output is correct
3 Correct 445 ms 8920 KB Output is correct
4 Correct 445 ms 8920 KB Output is correct
5 Incorrect 255 ms 6104 KB Output isn't correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 3692 KB Output is correct
2 Correct 97 ms 3692 KB Output is correct
3 Correct 102 ms 3692 KB Output is correct
4 Incorrect 64 ms 2404 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 5728 KB Output is correct
2 Correct 229 ms 5728 KB Output is correct
3 Correct 534 ms 10968 KB Output is correct
4 Incorrect 278 ms 7256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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