Submission #140565

#	Time	Username	Problem	Language	Result	Execution time	Memory
140565		HellAngel	Global Warming (CEOI18_glo)	C++14	100 / 100	71 ms	9336 KiB

glo

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 2e5 + 7;

int n, x, a[maxn], d[maxn], Max = 0, prf[maxn], suf[maxn], ans, Maxa = 0, b[maxn];

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
    cin >> n >> x;
    for(int i = 1; i <= n; i++) cin >> a[i], Maxa = max(Maxa, a[i]);
    for(int i = 1; i <= n; i++) b[i] = Maxa - a[i] + 1;
    Max = 0;
    d[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        int l = 0;
        int r = Max;
        while(l <= r)
        {
            int mid = l + r >> 1;
            if(a[i] > d[mid]) l = mid + 1;
            else r = mid - 1;
        }
        Max = max(Max, l);
        d[l] = a[i];
        prf[i] = l;
    }
    Max = 0;
    d[0] = 0;
    for(int i = n; i >= 1; i--)
    {
        int l = 0;
        int r = Max;
        while(l <= r)
        {
            int mid = l + r >> 1;
            if(b[i] > d[mid]) l = mid + 1;
            else r = mid - 1;
        }
        Max = max(Max, l);
        d[l] = b[i];
        suf[i] = l;
    }
    ans = Max;
    Max = 0;
    d[0] = LLONG_MIN;
    for(int i = 1; i < n; i++)
    {
        d[prf[i]] = a[i] - x;
        Max = max(Max, prf[i]);
        int l = 0;
        int r = Max;
        while(l <= r)
        {
            int mid = l + r >> 1;
            if(d[mid] < a[i + 1]) l = mid + 1;
            else r = mid - 1;
        }
        ans = max(ans, suf[i + 1] + r);
    }
    cout << ans;
}

Compilation message (stderr)

glo.cpp: In function 'int32_t main()':
glo.cpp:26:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int mid = l + r >> 1;
                       ~~^~~
glo.cpp:42:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int mid = l + r >> 1;
                       ~~^~~
glo.cpp:61:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int mid = l + r >> 1;
                       ~~^~~
glo.cpp:14:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:14:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

• 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