Submission #1096665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096665		Top1BUCODE	Global Warming (CEOI18_glo)	C++14	27 / 100	213 ms	10440 KiB

glo

#include <bits/stdc++.h>
using namespace std;
const int N=4e5+5;
int n,t[4*N],a[N],f[N],x,h,u,v,k,res; vector <int> ve;
void update(int id,int l,int r)
{
    if (l==r)
    {
        t[id]=h;
        return;
    }
    int m=(l+r)/2;
    if (u<=m) update(id*2,l,m); else update(id*2+1,m+1,r);
    t[id]=max(t[id*2],t[id*2+1]);
}
int get(int id,int l,int r)
{
    if (v<l) return 0;
    if (v>=r) return t[id];
    int m=(l+r)/2;
    return max(get(id*2,l,m),get(id*2+1,m+1,r));
}
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> x;
    x=abs(x);
    for (int i=1;i<=n;i++)
    {
        cin >> a[i];
        ve.push_back(a[i]);
        ve.push_back(a[i]+x);
    }
    sort(ve.begin(),ve.end());
    ve.resize(unique(ve.begin(),ve.end())-ve.begin());
    k=ve.size();
    for (int i=1;i<=n;i++)
    {
        v=lower_bound(ve.begin(),ve.end(),a[i]+x)-ve.begin();
        h=get(1,1,k)+1;
        u=v+1;
        if (f[u]<h)
        {
            f[u]=h;
            update(1,1,k);
            res=max(res,f[u]);
        }
        v=lower_bound(ve.begin(),ve.end(),a[i])-ve.begin();
        h=get(1,1,k)+1;
        u=v+1;
        if (f[u]<h)
        {
            f[u]=h;
            update(1,1,k);
            res-max(res,f[u]);
        }
    }
    cout << res;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:56:16: warning: value computed is not used [-Wunused-value]
   56 |             res-max(res,f[u]);
      |             ~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 17 / 17
• Subtask 7: 0 / 25