Submission #144675

#	Time	Username	Problem	Language	Result	Execution time	Memory
144675		nhamtan	Global Warming (CEOI18_glo)	C++14	100 / 100	1560 ms	46228 KiB

glo

#include<bits/stdc++.h>
using namespace std;

#define y1 as214
#define ii pair < int , int >
#define iii pair < int , ii >
#define iv pair < ii , ii >

#define fi first
#define se second
#define fr front()
#define pb push_back
#define t top()

#define FOR(i , x , n) for(int i = x ; i <= n ; ++i)
#define REP(i , n) for(int i = 0 ; i < n ; ++i)
#define FORD(i , x , n) for(int i = x ; i >= n ; --i)

#define ll long long
#define oo 2e9
#define int long long

const int N = 2e5 + 5;
int n , val , res;
int a[2 * N] , f[2 * N] , b[2 * N];
int st[8 * N];
unordered_map < int , int > m;

void up(int id , int l , int r , int i , int val)
{
    if(l > i || r < i)
        return;
    if(l == r)
    {
        st[id] = max(st[id] , val);
        return;
    }
    int mid = (l + r) / 2;
    up(id * 2 , l , mid , i , val);
    up(id * 2 + 1 , mid + 1 , r , i , val);
    st[id] = max(st[id * 2] , st[id * 2 + 1]);
}

int get(int id , int l , int r , int u , int v)
{
    if(l > v || r < u)
        return 0;
    else if(l >= u && r <= v)
        return st[id];
    int mid = (l + r) / 2;
    return max(get(id * 2 , l , mid , u , v) , get(id * 2 + 1 , mid + 1 , r , u , v));
}

main()
{
    //freopen("GLO.inp","r",stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> val;
    FOR(i , 1 , n)
    {
        cin >> a[i];
        b[i] = a[i];
        a[i + n] = b[i + n] = a[i] + val;
    }


    sort(b + 1 , b + 1 + 2 * n);
    b[0] = -oo;
    int r = 0;
    FOR(i , 1 , 2 * n)
    {
        if(b[i] != b[i - 1])
            m[b[i]] = ++r;
        else
            m[b[i]] = r;
    }

    FORD(i , n , 1)
    {
        f[i] = get(1 , 1 , 2 * n , m[a[i + n]] + 1 , 2 * n) + 1;
        up(1 , 1 , 2 * n , m[a[i + n]] , f[i]);
    }
    memset(st , 0 , sizeof(st));
    FOR(i , 1 , n + 1)
    {
        res = max(res , get(1 , 1 , 2 * n , 1 , m[a[i + n]] - 1) + f[i]);
        up(1 , 1 , 2 * n , m[a[i]] , get(1 , 1 , 2 * n , 1 , m[a[i]] - 1) + 1);
    }
     /// hết phần dương.



    m.clear();
    FOR(i , 1 , n)
        a[i + n] = b[i + n] = a[i] - val;
    sort(b + 1 , b + 1 + 2 * n);
    b[0] = -oo;
    r = 0;
    FOR(i , 1 , 2 * n)
    {
        if(b[i] != b[i - 1])
            m[b[i]] = ++r;
        else
            m[b[i]] = r;
    }

    memset(st , 0 , sizeof(st));
    FOR(i , 1 , n)
    {
        f[i] = get(1 , 1 , 2 * n , 1 , m[a[i + n]] - 1) + 1;
        up(1 , 1 , 2 * n , m[a[i + n]] , f[i]);
    }
    memset(st , 0 , sizeof(st));
    FORD(i , n , 0)
    {
        res = max(res , get(1 , 1 , 2 * n , m[a[i + n]] + 1 , n) + f[i]);
        up(1 , 1 , 2 * n , m[a[i]] , get(1 , 1 , 2 * n , m[a[i]] + 1 , n) + 1);
    }

    cout << res;
}

Compilation message (stderr)

glo.cpp:54:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

• 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