제출 #217873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
217873		PeppaPig	Global Warming (CEOI18_glo)	C++14	100 / 100	182 ms	7268 KiB

glo

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+5;

int t[N << 1];

void update(int x, int k) {
    for(t[x += N] = k; x != 1; x >>= 1)
        t[x >> 1] = max(t[x], t[x ^ 1]);
}

int query(int l, int r) {
    int ret = 0;
    for(l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
        if(l & 1) ret = max(ret, t[l++]);
        if(r & 1) ret = max(ret, t[--r]);
    }
    return ret;
}

int n, x;
int A[N], pos[N];
vector<int> coord;

int main() {
    scanf("%d %d", &n, &x);
    vector<int> V;
    for(int i = 1; i <= n; i++) {
        scanf("%d", A + i);
        coord.emplace_back(A[i]), V.emplace_back(i);
    }
    sort(coord.begin(), coord.end());
    sort(V.begin(), V.end(), [&](int a, int b) { return A[a] < A[b]; });
    for(int i = 0; i < n; i++) pos[V[i]] = i + 1;

    V.clear();
    for(int i = 1, z; i <= n; i++) {
        if(V.empty() || V.back() < A[i]) V.emplace_back(A[i]), z = V.size();
        else {
            auto it = lower_bound(V.begin(), V.end(), A[i]);
            *it = A[i], z = it - V.begin() + 1;
        }
        update(pos[i], z); 
    }
    int ans = V.size();
    V.clear();
    for(int i = n, z; i; i--) {
        update(pos[i], 0);
        if(V.empty() || V.back() > A[i]) V.emplace_back(A[i]), z = V.size();
        else {
            auto it = lower_bound(V.begin(), V.end(), A[i], greater<int>());
            *it = A[i], z = it - V.begin() + 1;
        }
        int idx = lower_bound(coord.begin(), coord.end(), A[i] + x) - coord.begin();
        ans = max(ans, z + query(1, idx));
    }
    printf("%d\n", ans);

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

glo.cpp: In function 'int main()':
glo.cpp:28: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:31: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