Submission #698027

#TimeUsernameProblemLanguageResultExecution timeMemory
698027winthemcut3Global Warming (CEOI18_glo)C++14
10 / 100
122 ms10180 KiB
#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define PB push_back
#define ALL(v) (v).begin(), (v).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define fi   first
#define se   second
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;

/** END OF TEMPLATE **/

const int mxN = 2e5 + 5;
int n, d;
int f1[mxN], f2[mxN], a[mxN], b[mxN];
struct fenwick {
    vector<int> bit;
    fenwick(int t) { bit.resize(t + 1, 0); }
    void update(int id, int val) {
        for(id; id <= 2*n; id += id&-id) bit[id] = max(bit[id], val);
    }
    ll get(int id) {
        int temp = 0;
        for(id; id > 0; id -= id&-id) temp = max(temp, bit[id]);
        return temp;
    }
};

int main()
{
    FastIO;
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    cin >> n >> d;
    vector<int> t;
    FOR(i, 1, n) {
        cin >> a[i];
        t.PB(a[i]); t.PB(a[i] + d);
    }
    sort(ALL(t));
    t.erase(unique(ALL(t)), t.end());
    FOR(i, 1, n)
        a[i] = lower_bound(ALL(t), a[i]) - t.begin() + 1,
        b[i] = lower_bound(ALL(t), a[i] + d) - t.begin() + 1;

    fenwick T1(2*n);
    FOR(i, 1, n) {
        f1[i] = T1.get(a[i]-1) + 1;
        T1.update(a[i], f1[i]);
    }
    fenwick T(2*n);
    FOR(i, 1, n) {
        f2[i] = T.get(b[i] - 1) + 1;
        T.update(a[i], f1[i]);
        T.update(b[i], f2[i]);
    }
    int res = 0;
    FOR(i, 1, n)
        res = max(res, max(f1[i], f2[i]));
    cout << res;

    return 0;
}

/*

*/

Compilation message (stderr)

glo.cpp: In member function 'void fenwick::update(int, int)':
glo.cpp:22:13: warning: statement has no effect [-Wunused-value]
   22 |         for(id; id <= 2*n; id += id&-id) bit[id] = max(bit[id], val);
      |             ^~
glo.cpp: In member function 'long long int fenwick::get(int)':
glo.cpp:26:13: warning: statement has no effect [-Wunused-value]
   26 |         for(id; id > 0; id -= id&-id) temp = max(temp, bit[id]);
      |             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...