Submission #144679

#	Time	Username	Problem	Language	Result	Execution time	Memory
144679		nhamtan	Global Warming (CEOI18_glo)	C++14	100 / 100	1525 ms	59592 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[3 * N] , f[N] , b[3 * N] , dp[N];
int st[12 * 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;
        b[i + 2 * n] = a[i + 2 * n] = a[i] - val;
    }
 
 
    sort(b + 1 , b + 1 + 3 * n);
    b[0] = -oo;
    int r = 0;
    FOR(i , 1 , 3 * 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 , r , m[a[i]] + 1 , r) + 1;
        up(1 , 1 , r , m[a[i]] , f[i]);
    }

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