Submission #823359

#	Time	Username	Problem	Language	Result	Execution time	Memory
823359		MohamedAhmed04	Global Warming (CEOI18_glo)	C++14	100 / 100	230 ms	14992 KiB

glo

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200010 * 2;
const long long inf = 2e9 ;
int arr[MAX] , arr2[MAX] , len[MAX] , tree[4 * MAX] ;

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

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0) ;
    int n , x ;
    cin>>n>>x ;
    vector< pair<int , int> >vp ;
    for(int i = 1 ; i <= n ; ++i)
    {
        cin>>arr2[i] ;
        arr2[i] += x ;
        vp.push_back({arr2[i] , i}) ;
        vp.push_back({arr2[i]-x , n+i});
    }
    sort(vp.begin() , vp.end());
    int idx = 1 ;
    for(int i = 0 ; i < vp.size() ; ++i)
    {
        if(i != 0)
        {
            if(vp[i].first == vp[i-1].first)
                --idx;
        }
        arr[vp[i].second] = idx ;
        idx++ ;
    }
    int ans = 0 ;
    for(int i = n ; i > 0 ; --i)
    {
        len[i+n] = query(1 , 1 , n*2+1 , arr[i+n] + 1 , n*2+1) ;
        int a = query(1 , 1 , n * 2 + 1 , arr[i]+1 , n * 2 + 1) + 1;
        update(1 , 1 , n * 2 + 1 , arr[i] , a) ;
    }
    memset(tree , 0 , sizeof(tree));
    for(int i = n+1 ; i <= n*2 ; ++i)
    {
        int a = query(1 , 1 , n * 2 + 1 , 1 , arr[i]-1) + 1;
        update(1 , 1 , n * 2 + 1 , arr[i] , a) ;
        ans = max(ans , a + len[i]);
    }
    return cout<<ans<<"\n" , 0 ;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i = 0 ; i < vp.size() ; ++i)
      |                     ~~^~~~~~~~~~~

• 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