Submission #881256

#	Time	Username	Problem	Language	Result	Execution time	Memory
881256		votranngocvy	Global Warming (CEOI18_glo)	C++14	100 / 100	73 ms	18120 KiB

glo

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

#define ll long long
#define piii pair<ll,pair<int,int>>
#define fi first
#define se second
#define mp make_pair
const int N = 4e5 + 5;
int n,f[N],g[N],bit[N],val[N];
ll a[N],b[N],x;

void compress() {
    vector<piii>vec;
    for (int i = 1; i <= n; i++) {
        vec.push_back(mp(a[i],mp(i,1)));
        vec.push_back(mp(b[i],mp(i,2)));
    }
    sort(vec.begin(),vec.end());
    val[0] = 1;
    if (vec[0].se.se == 1) a[vec[0].se.fi] = val[0];
    else b[vec[0].se.fi] = val[0];
    for (int i = 1; i < vec.size(); i++) {
        if (vec[i].fi == vec[i - 1].fi) val[i] = val[i - 1];
        else val[i] = i + 1;
        if (vec[i].se.se == 1) a[vec[i].se.fi] = val[i];
        else b[vec[i].se.fi] = val[i];
    }
}

void update(int i,int x) {
    for (; i < N; i += i & (-i)) bit[i] = max(bit[i],x);
}

void update2(int i,int x) {
    for (; i > 0; i -= i & (-i)) bit[i] = max(bit[i],x);
}

int get(int i) {
    int ans = 0;
    for (; i > 0; i -= i & (-i)) ans = max(ans,bit[i]);
    return ans;
}

int get2(int i) {
    int ans = 0;
    for (; i < N; i += i & (-i)) ans = max(ans,bit[i]);
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i] - x;
    }
    compress();
    for (int i = 1; i <= n; i++) {
        f[i] = get(a[i] - 1) + 1;
        update(a[i],f[i]);
    }
    memset(bit,0,sizeof(bit));
    for (int i = n; i > 0; i--) {
        g[i] = get2(b[i] + 1) + 1;
        update2(a[i],get2(a[i] + 1) + 1);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans,f[i] + g[i] - 1);
    cout << ans << "\n";
}

Compilation message (stderr)

glo.cpp: In function 'void compress()':
glo.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i = 1; i < vec.size(); 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