제출 #1272866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272866		cokalhado	Global Warming (CEOI18_glo)	C++20	100 / 100	329 ms	23188 KiB

glo

// https://oj.uz/problem/view/CEOI18_glo
// it will always be >= to choose a point and to the right of it increase all by x
// when doing compression, find your value and also the value of you+x
// do dp(i, 0) -> max from me down. dp(i, 1) -> max from me+x down
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int maxn = 2e5+10;
int n, x;
pair<int, int> ar[maxn]; // value and value+x
int ans;
int tr[8*maxn][2];

void update(int no, int l, int r, int pos, int val, bool b)
{
    if(l == r) tr[no][b] = max(tr[no][b], val);
    else
    {
        int lc = 2*no; int rc = 2*no+1; int mid = (l+r)/2;
        if(pos <= mid) update(lc, l, mid, pos, val, b);
        else update(rc, mid+1, r, pos, val, b);
        tr[no][b] = max(tr[lc][b], tr[rc][b]);
    }
}

int query(int no, int l, int r, int L, int R, bool b)
{
    if(r < L || R < l) return 0;
    else if(L <= l && r <= R) return tr[no][b];
    else
    {
        int lc = 2*no; int rc = 2*no+1; int mid = (l+r)/2;
        return max(query(lc, l, mid, L, R, b), query(rc, mid+1, r, L, R, b));
    }
}

int32_t main()
{
    cin >> n >> x;
    vector<int> c;
    for(int i = 1; i <= n; i++)
    {
        int t; cin >> t;
        c.push_back(t);
        c.push_back(t+x);
        ar[i] = {t, t+x};
    }
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());
    for(int i = 1; i <= n; i++)
    {
        ar[i].first = upper_bound(c.begin(), c.end(), ar[i].first) - c.begin();
        ar[i].second = upper_bound(c.begin(), c.end(), ar[i].second) - c.begin();
    }

    for(int i = 1; i <= n; i++)
    {
        // dp0 = query0(0, ar[i].f-1)+1
        int dp0 = query(1, 0, 2*n, 0, ar[i].first-1, 0)+1;
        // dp1 = max(query0(0, ar[i].s-1), query1(0, ar[i].s-1))+1
        int dp1 = max(query(1, 0, 2*n, 0, ar[i].second-1, 0), query(1, 0, 2*n, 0, ar[i].second-1, 1))+1;
        // update0(ar[i].f dp0)
        update(1, 0, 2*n, ar[i].first, dp0, 0);
        // update1(ar[i].s dp1)
        update(1, 0, 2*n, ar[i].second, dp1, 1);
        // ans = max(ans, dp1)
        ans = max(ans, dp1);
    }
    cout << ans;
    return 0;
}

• 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