Submission #17050957


Source Code Expand

Copy
#include<bits/stdc++.h>
#include<atcoder/all>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; using namespace atcoder;
void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
#define def 0
template<class V, int NV> struct SegTree { //[l,r)
    V comp(V& l, V& r) { return max(l, r); };

    vector<V> val; SegTree() { val = vector<V>(NV * 2, def); }
    V get(int x, int y, int l = 0, int r = NV, int k = 1) {
        if (r <= x || y <= l)return def; if (x <= l && r <= y)return val[k];
        auto a = get(x, y, l, (l + r) / 2, k * 2);
        auto b = get(x, y, (l + r) / 2, r, k * 2 + 1);
        return comp(a, b);
    }
    void update(int i, V v) {
        i += NV; val[i] = v;
        while (i > 1) i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]);
    }
    void add(int i, V v) { update(i, val[i + NV] + v); }
    V operator[](int x) { return get(x, x + 1); }
};
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     @hamayanhamayan0
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/














int N, K, A[301010];
SegTree<int, 1 << 19> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];

    rep(i, 0, N) {
        int ma = st.get(max(0, A[i] - K), min(301010, A[i] + K + 1));
        st.update(A[i], ma + 1);
    }

    int ans = st.get(0, 301010);
    cout << ans << endl;
}





Submission Info

Submission Time
Task D - Flat Subsequence
User hamayanhamayan
Language C++ (GCC 9.2.1 with AC Library)
Score 400
Code Size 2472 Byte
Status AC
Exec Time 128 ms
Memory 8512 KB

Compile Error

./Main.cpp: In member function ‘V SegTree<V, NV>::get(int, int, int, int, int)’:
./Main.cpp:20:9: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
   20 |         if (r <= x || y <= l)return def; if (x <= l && r <= y)return val[k];
      |         ^~
./Main.cpp:20:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
   20 |         if (r <= x || y <= l)return def; if (x <= l && r <= y)return val[k];
      |                                          ^~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 1
AC × 31
Set Name Test Cases
Sample example0.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, example0.txt
Case Name Status Exec Time Memory
000.txt AC 109 ms 8448 KB
001.txt AC 33 ms 7244 KB
002.txt AC 42 ms 7564 KB
003.txt AC 66 ms 7920 KB
004.txt AC 25 ms 7300 KB
005.txt AC 46 ms 7984 KB
006.txt AC 70 ms 7772 KB
007.txt AC 104 ms 8036 KB
008.txt AC 39 ms 7708 KB
009.txt AC 43 ms 7708 KB
010.txt AC 94 ms 8368 KB
011.txt AC 114 ms 8416 KB
012.txt AC 123 ms 8476 KB
013.txt AC 125 ms 8476 KB
014.txt AC 113 ms 8512 KB
015.txt AC 100 ms 8460 KB
016.txt AC 112 ms 8448 KB
017.txt AC 113 ms 8460 KB
018.txt AC 103 ms 8448 KB
019.txt AC 115 ms 8476 KB
020.txt AC 86 ms 8368 KB
021.txt AC 97 ms 8500 KB
022.txt AC 94 ms 8500 KB
023.txt AC 128 ms 8340 KB
024.txt AC 105 ms 8364 KB
025.txt AC 87 ms 8500 KB
026.txt AC 87 ms 8472 KB
027.txt AC 106 ms 8408 KB
028.txt AC 70 ms 8500 KB
029.txt AC 74 ms 8500 KB
example0.txt AC 6 ms 7212 KB