Submission #539057

#	Time	Username	Problem	Language	Result	Execution time	Memory
539057		kianaRZV	Financial Report (JOI21_financial)	C++14	100 / 100	725 ms	39828 KiB

Main

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

const int maxn = 3e5 + 10, mod = 1e9 + 7;
int n, d;
int a[maxn], l[maxn], r[maxn], dp[maxn], seg[maxn << 2];
struct query{
    int val, id;
}q[maxn];
set <int> st, have;

bool cmp(query a, query b) {
    if (a.val != b.val)
        return a.val < b.val;
    return a.id > b.id;
}

void add(int id, int l, int r, int pos, int x) {
    if (l > pos || r <= pos)
        return;
    if (r - l < 2) {
        seg[id] = x;
        return;
    }
    int mid = l + r >> 1;
    add(2 * id + 1, l, mid, pos, x);
    add(2 * id + 2, mid, r, pos, x);
    seg[id] = max(seg[2 * id + 1], seg[2 * id + 2]);
}

int get(int id, int l, int r, int ql, int qr) {
    if (l >= qr || ql >= r)
        return 0;
    if (ql <= l && r <= qr)
        return seg[id];
    int mid = l + r >> 1;
    return max(get(2 * id + 1, l, mid, ql, qr), get(2 * id + 2, mid, r, ql, qr));
}

void L(int id) {
    if (~l[id])
        r[l[id]] = id;
}

void R(int id) {
    if (r[id] != n) {
        l[r[id]] = id;
        if (r[id] - id <= d)
            st.erase(r[id]);
    }
}

void read_input() {
    cin >> n >> d;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        q[i] = {a[i], i};
    }
}

void solve() {
    int ans = 0;
    sort(q, q + n, cmp);
    have.insert(-1), have.insert(n);
    for (int i = 0; i < n; i++) {
        int id = q[i].id;
        dp[id] = 1;
        auto it = have.lower_bound(id);
        r[id] = *it, it--, l[id] = *it;
        have.insert(id);
        R(id), L(id);
        if (id - l[id] > d)
            st.insert(id);
        if (id) {
            it = st.upper_bound(id);
            if (it == st.begin())
                dp[id] = max(dp[id], get(0, 0, n, 0, id) + 1);
            else {
                it--;
                int loc = max(*it, 0ll);
                if (loc ^ id)
                    dp[id] = max(dp[id], get(0, 0, n, loc, id) + 1);
            }
        }
        add(0, 0, n, id, dp[id]);
        ans = max(ans, dp[id]);
    }
    cout << ans;

}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    read_input(), solve();
}

Compilation message (stderr)

Main.cpp: In function 'void add(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:26:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     int mid = l + r >> 1;
      |               ~~^~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35