Submission #257545

#	Time	Username	Problem	Language	Result	Execution time	Memory
257545		anonymous	Global Warming (CEOI18_glo)	C++14	100 / 100	91 ms	5844 KiB

glo

#include <iostream>
#define MAXN 200005
using namespace std;
int N, X, Ans, A[MAXN], Op[MAXN][2];
int dp[MAXN], dp2[MAXN]; //min height for i length in prefix, max height for i length in suffix

int main() {
    //freopen("gloin.txt","r",stdin);
    scanf("%d %d",&N,&X);
    for (int i=1; i<=N; i++) {
        scanf("%d",&A[i]);
        dp[i] = 2e9 + 1;
    }
    dp2[0] = 2e9 + 1;

    for (int i=1; i <= N; i++) {
        int lo = 0, hi = N;
        while (lo + 1 != hi) {
            int mid = (lo + hi) >> 1;
            if (dp[mid] >= A[i]) {hi = mid;}
            else {lo = mid;}
        }
        Op[i][0] = lo+1, Op[i][1] = dp[lo+1];
        dp[lo+1] = A[i];
        Ans = max(Ans, lo+1);
    }

    for (int i=N; i >= 1; i--) {
        int lo = 0, hi = N;
        while (lo + 1 != hi) {
            int mid = (lo + hi) >> 1;
            if (dp2[mid] <= A[i]) {hi = mid;}
            else {lo = mid;}
        }
        dp2[lo+1] = A[i];
        dp[Op[i][0]] = Op[i][1];
        int lo2 = 0, hi2 = N;
        while (lo2 + 1 != hi2) {
            int mid = (lo2 + hi2) >> 1;
            if (dp[mid] >= A[i] + X) {hi2 = mid;}
            else {lo2 = mid;}
        }
        Ans = max(Ans, lo2 + lo + 1);
    }

    printf("%d", Ans);
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&X);
     ~~~~~^~~~~~~~~~~~~~~
glo.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&A[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