Submission #653716

#	Time	Username	Problem	Language	Result	Execution time	Memory
653716		PagodePaiva	Global Warming (CEOI18_glo)	C++14	38 / 100	2098 ms	21644 KiB

glo

#include<bits/stdc++.h>
#define int long long 
#define ms(v) memset(v, -1, sizeof v)
#define pi pair<int, int>
#define pb push_back
#define fr first
#define sc second
#define all(x) x.begin(), x.end()
#define INF (int) 1e15
#define mp make_pair
#define itn int
#define N 200010

using namespace std;

int n, x;
int v[N];
int dp[N][2];
vector <pi> sorted;

struct Seg{
    int tree[4*N];

    int join(int a, int b){
        return max(a, b);
    }

    void build(int node, int l, int r){
        if(l == r){
            tree[node] = 0;
            return;
        }

        int mid = (l+r) >> 1;

        build(2*node, l, mid);
        build(2*node+1, mid+1, r);

        tree[node] = join(tree[2*node], tree[2*node+1]);

        return;
    }

    void update(int node, int l, int r, int pos, int val){
        if(l == r){
            tree[node] = val;
            return;
        }

        int mid = (l+r) >> 1;

        if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
        else update(2*node+1, mid+1, r, pos, val);
    
        tree[node] = join(tree[2*node], tree[2*node+1]);

        return;
    }

    int query(int node, int l, int r, int tl, int tr){
        if(l <= tl and tr <= r) return tree[node];
        if(l > tr or r < tl) return -1;

        int mid = (tl+tr) >> 1;

        return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
    }
} seg;

void compress(){
    map <int, int> m;
    sort(all(sorted));

    for(int i = 0;i < n;i++){
        if(m[sorted[i].fr] == 0){
            m[sorted[i].fr] = i+1;
        }

        sorted[i].fr = m[sorted[i].fr];
    }

    for(int i = 0;i < n;i++){
        v[sorted[i].sc] = sorted[i].fr;
    }

    return;
}

void sub4(){
    compress();

    int res = 0;

    seg.build(1, 1, n);


    for(int i = 1;i <= n;i++){
        int aux;
        aux = seg.query(1, 1, v[i]-1, 1, n) + 1;
        seg.update(1, 1, n, v[i], aux);
    }

    cout << seg.query(1, 1, n, 1, n) << "\n";

    return;
}

void sub3(){
    dp[0][0] = 0;
    dp[0][1] = 0;

    for(int i = 1;i <= n;i++){
        dp[i][0] = 1;
        dp[i][1] = 1;
        for(int j = 1;j < i;j++){
            dp[i][0] = max(dp[i][0], (v[i] > v[j] ? dp[j][0] + 1 : -INF));
            dp[i][1] = max(dp[i][1], max((v[i] > v[j] - x ? dp[j][0] + 1 : -INF), (v[i] > v[j] ? dp[j][1] + 1 : -INF)));
        }
    }

    int res = 0;

    for(int i = 1;i <= n;i++){
        res = max(dp[i][1], res);   
    }

    cout << res << "\n";
}
int32_t main(){
    ios::sync_with_stdio(false); cin.tie(0);

    cin >> n >> x;

    for(int i = 1;i <= n;i++){
        cin >> v[i];
        sorted.pb({v[i], i});
    }

    if(x == 0 and n > 1000){
        sub4();
    }

    else{
        sub3();
    }

    return 0;   
}

Compilation message (stderr)

glo.cpp: In function 'void sub4()':
glo.cpp:92:9: warning: unused variable 'res' [-Wunused-variable]
   92 |     int res = 0;
      |         ^~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25