Submission #448305

#	Time	Username	Problem	Language	Result	Execution time	Memory
448305		nickyrio	Financial Report (JOI21_financial)	C++17	5 / 100	203 ms	10948 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 100;

int a[N], perm[N], f[N], IT[N << 2];

void Up(int k, int l, int r, int u, int v, int x) {
    if (l > v || r < u) return;
    if (u <= l && r <= v) { IT[k] = max(IT[k], x);  return; }
    int m = l + r >> 1;
    Up(k << 1, l, m, u, v, x);
    Up(k << 1 | 1, m + 1, r, u, v, x);
} 

int Query(int k, int l, int r, int u) {
    if (l == r) return IT[k];
    int m = l + r >> 1;
    if (u <= m) return max(IT[k], Query(k << 1, l, m, u));
    return max(IT[k], Query(k << 1 | 1, m + 1, r, u));
}

int main() {
  ios::sync_with_stdio(false); cin.tie(NULL);
    int n, d;
    cin >> n >> d;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        perm[i] = i;
    }
    sort(perm, perm + n, [](int x, int y) {
        return a[x] < a[y];
    });
    int ans = 0;
    int j = 0;
    for (int i = 0; i < n; ++i) {
        int id = perm[i];
        if (i && a[perm[i]] != a[perm[i - 1]]) {
            // Update
            while (j < i) {
                int l = perm[j] + 1, r = min(n, perm[j] + d + 1);
                // cerr << "Update" << l << ' ' << r << ' ' << f[perm[j]] << '\n';
                Up(1, 1, n, l, r, f[perm[j++]]);

            }
        }

        // // Query
        f[id] = Query(1, 1, n, id + 1) + 1;
        // cerr << i << ' ' << id << ' ' << a[id] << ' ' << f[id] << '\n';
        ans = max(ans, f[id]);
    }
    cout << ans << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'void Up(int, int, int, int, int, int)':
Main.cpp:12:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |     int m = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'int Query(int, int, int, int)':
Main.cpp:19:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |     int m = l + r >> 1;
      |             ~~^~~

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