Submission #430634

#	Time	Username	Problem	Language	Result	Execution time	Memory
430634		Runtime_error_	Global Warming (CEOI18_glo)	C++14	100 / 100	1504 ms	29736 KiB

glo

#include <bits/stdc++.h>
#define ll long long
#define le node+node
#define ri node+node+1
#define mid (l+r)/2
using namespace std;
const int inf = 4e5+9;
int n,k,a[inf],cnt,tree[inf<<2],lis[inf],lds[inf];
map<int,int> mp;

void update(int node,int l,int r,int idx,int val){
    if(l == r)
        return void(tree[node] = max(tree[node],val));
    if(idx <= mid)
        update(le,l,mid,idx,val);
    else
        update(ri,mid+1,r,idx,val);
    tree[node] = max(tree[le],tree[ri]);
}

int query(int node,int l,int r,int x,int y){
    if(l>r || r<x || l>y || x>y)
        return 0;
    if(l>=x && r<=y)
        return tree[node];
    return max(query(le,l,mid,x,y),query(ri,mid+1,r,x,y));
}


int main(){

    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i),mp[a[i]],mp[a[i]-k+1];

    for(auto &o:mp)
        o.second = ++cnt;

    for(int i=1;i<=n;i++){
        lis[i]  = 1 + query(1,1,cnt,1,mp[a[i]]-1);
        update(1,1,cnt,mp[a[i]],lis[i]);
        //cout<<lis[i]<<" ";
    }
    memset(tree,0,sizeof(tree));

    for(int i=n;i>=1;i--){
        lds[i] = 1 + query(1,1,cnt,mp[a[i]]+1,cnt);
        update(1,1,cnt,mp[a[i]],lds[i]);
    }
    int ans = 0;
    memset(tree,0,sizeof(tree));
    for(int i=n;i>=1;i--)
        ans = max(ans,lis[i] + query(1,1,cnt,mp[a[i]-k+1],mp[a[i]])),update(1,1,cnt,mp[a[i]],lds[i]);

    cout<<ans<<endl;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
glo.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf("%d",a+i),mp[a[i]],mp[a[i]-k+1];
      |         ~~~~~^~~~~~~~~~

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