Submission #886655

#	Time	Username	Problem	Language	Result	Execution time	Memory
886655		Caubethieunang	Global Warming (CEOI18_glo)	C++14	58 / 100	219 ms	15116 KiB

glo

#include <bits/stdc++.h>
#define ll long long
#define LOG 19
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1)
#define FIRST_BIT(mask) __builtin_ctz((mask)&(-mask))
#define ERASE_BIT(mask) (mask)^((mask)&(-mask))
#define left _left
#define right _right
#define task "t"
using namespace std;
const ll INF=1e18;
const int iat=1e6+9;
const int mod=1e9+7;
void fast_IO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
}
int n,x,t[iat],tx[iat],sz,store[iat];
void compress()
{
    vector <int> v;
    for(int i=1; i<=n; i++)
    {
        v.push_back(t[i]);
        v.push_back(t[i]+x);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    sz=v.size();
    for(int i=1; i<=n; i++)
    {
        tx[i]=lower_bound(v.begin(),v.end(),t[i]+x)-v.begin()+1;
        t[i]=lower_bound(v.begin(),v.end(),t[i])-v.begin()+1;
    }
}
struct Segment
{
    int st[iat];
    void init()
    {
        memset(st,0,sizeof(st));
    }
    void update(int id, int l, int r, int pos, int val)
    {
        if(l==r)
        {
            st[id]=max(st[id],val);
            return;
        }
        int mid=(l+r)/2;
        if(pos<=mid)update(2*id,l,mid,pos,val);
        else update(2*id+1,mid+1,r,pos,val);
        st[id]=max(st[2*id],st[2*id+1]);
    }
    int getMax(int id, int l, int r, int u, int v)
    {
        if(u>v || l>v || r<u)return 0;
        if(u<=l && r<=v)return st[id];
        int mid=(l+r)/2;
        return max(getMax(2*id,l,mid,u,v),getMax(2*id+1,mid+1,r,u,v));
    }
}tree;
signed main()
{
    fast_IO();
    cin>>n>>x;
    for(int i=1; i<=n; i++)cin>>t[i];
    compress();
    int ans=0;
    for(int i=n; i>=1; i--)
    {
        store[i]=tree.getMax(1,1,sz,tx[i]+1,sz)+1;
        tree.update(1,1,sz,tx[i],store[i]);
        ans=max(ans,store[i]);
    }
    tree.init();
    for(int i=1; i<=n; i++)
    {
        ans=max(ans,store[i]+tree.getMax(1,1,sz,1,tx[i]-1));
        int tmp=tree.getMax(1,1,sz,1,t[i]-1)+1;
        tree.update(1,1,sz,t[i],tmp);
    }
    cout<<ans;
}

Compilation message (stderr)

glo.cpp: In function 'void fast_IO()':
glo.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
glo.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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