Submission #717187

#	Time	Username	Problem	Language	Result	Execution time	Memory
717187		PanosPask	Global Warming (CEOI18_glo)	C++14	0 / 100	51 ms	5240 KiB

glo

#include <bits/stdc++.h>
#define MAXN 200000

using namespace std;

int n, x;
int a[MAXN + 2];

int dp[MAXN + 2];

int inc_lis[MAXN + 2];
int dec_lis[MAXN + 2];
bool cont[MAXN + 2];

int main(void)
{
    scanf("%d %d", &n, &x);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }

    for (int i = 0; i <= n + 1; i++) {
        dp[i] = INT_MAX;
    }
    dp[0] = INT_MIN;
    for (int i = 1; i <= n; i++) {
        int curval = a[i];

        int l = 0;
        int r = n;
        while (r > l + 1) {
            int mid = (l + r) / 2;
            if (dp[mid] < curval)
                l = mid;
            else 
                r = mid;
        }

        dp[l+1] = curval;
        inc_lis[i] = l+1;
    }

    for (int i = 0; i <= n; i++)
        dp[i] = INT_MIN;
    dp[n+1] = INT_MAX;
    dec_lis[n+1] = 0;
    for (int i = n; i >= 1; i--) {
        int curval = a[i];
        int l = 0;
        int r= n+1;
        while (r > l + 1) {
            int mid = (l + r) / 2;
            if (dp[mid] > curval)
                r = mid;
            else 
                l = mid;
        }

        dp[r-1] = curval;
        if (dec_lis[i+1] < n - (r-1)) {
            dec_lis[i] = n - (r-1);
            cont[i] = true;
        }
        else {
            dec_lis[i] = dec_lis[i+1];
            cont[i] = false;
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, inc_lis[i] + dec_lis[i] - cont[i]); // Avoid doublecounting i

    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%d %d", &n, &x);
      |     ~~~~~^~~~~~~~~~~~~~~~~
glo.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25