Submission #140531

#	Time	Username	Problem	Language	Result	Execution time	Memory
140531		HellAngel	Global Warming (CEOI18_glo)	C++14	10 / 100	63 ms	8612 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;

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];
    for(int i = 1; i <= n; i++) d[i] = LLONG_MAX;
    Max = 0;
    d[0] = -1;
    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] = min(d[l], a[i]);
        prf[i] = l;
    }
    for(int i = 1; i <= n; i++) suf[i] = Max + 1 - prf[i];
    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:46: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: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25