Submission #95111

#	Time	Username	Problem	Language	Result	Execution time	Memory
95111		onjo0127	Global Warming (CEOI18_glo)	C++11	100 / 100	448 ms	17384 KiB

glo

#include <bits/stdc++.h>
using namespace std;

struct MaxSegtree {
    vector<int> tree;
    MaxSegtree(int N) {
        tree.resize(4*N);
    }
    void upd(int idx, int s, int e, int x, int y) {
        if(x < s || e < x) return;
        if(s == e) {
            tree[idx] = y;
            return;
        }
        int m = s+e >> 1;
        upd(idx*2, s, m, x, y);
        upd(idx*2+1, m+1, e, x, y);
        tree[idx] = max(tree[idx*2], tree[idx*2+1]);
    }
    int Max(int idx, int s, int e, int l, int r) {
        if(r < s || e < l) return 0;
        if(l <= s && e <= r) return tree[idx];
        int m = s+e >> 1;
        return max(Max(idx*2, s, m, l, r), Max(idx*2+1, m+1, e, l, r));
    }
};

vector<int> S;
int A[200009];

inline int get(int x) {
    return lower_bound(S.begin(), S.end(), x) - S.begin() + 1;
}

int main() {
    int N, x; scanf("%d%d",&N,&x);
    for(int i=1; i<=N; i++) {
        scanf("%d",&A[i]);
        S.push_back(A[i]);
        S.push_back(A[i] + x);
    }
    sort(S.begin(), S.end()); S.resize(unique(S.begin(), S.end()) - S.begin());
    MaxSegtree S1(2*N), S2(2*N);
    int ans = 0;
    for(int i=1; i<=N; i++) {
        int m1 = S1.Max(1, 1, 2*N, 1, get(A[i]) - 1) + 1;
        int m2 = max(S1.Max(1, 1, 2*N, 1, get(A[i] + x) - 1), S2.Max(1, 1, 2*N, 1, get(A[i] + x) - 1)) + 1;
        S1.upd(1, 1, 2*N, get(A[i]), m1); S2.upd(1, 1, 2*N, get(A[i] + x), m2);
        ans = max({ans, m1, m2});
    }
    printf("%d",ans);
    return 0;
}

Compilation message (stderr)

glo.cpp: In member function 'void MaxSegtree::upd(int, int, int, int, int)':
glo.cpp:15:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = s+e >> 1;
                 ~^~
glo.cpp: In member function 'int MaxSegtree::Max(int, int, int, int, int)':
glo.cpp:23:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = s+e >> 1;
                 ~^~
glo.cpp: In function 'int main()':
glo.cpp:36:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int N, x; scanf("%d%d",&N,&x);
               ~~~~~^~~~~~~~~~~~~~
glo.cpp:38: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