Submission #608977

#	Time	Username	Problem	Language	Result	Execution time	Memory
608977		Duy_e	Financial Report (JOI21_financial)	C++14	100 / 100	379 ms	61492 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define st first
#define nd second
#define file "test"
using namespace std;
const long long INF = 1e18;
const long long N = 3e5 + 100;

int n, a[N], sp[20][N], sp2[20][N], d, L[N], R[N], save[N];
pii b[N];

struct segment {
    int st[4 * N];

    void init() {
        memset(st, 0, sizeof st);
    }

    void upd(int id, int l, int r, int i, int v) {
        if (l > i || r < i) return;
        if (l == r) {
            st[id] = max(st[id], v);
            return;
        }

        int mid = l + r >> 1;
        upd(id << 1, l, mid, i, v); upd(id << 1 | 1, mid + 1, r, i, v);
        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }

    void upd(int i, int v) {
        upd(1, 1, n, i, v);
    }

    int get(int id, int l, int r, int lef, int rig) {
        if (l > rig || r < lef) return 0;
        if (lef <= l && r <= rig) return st[id];
        int mid = l + r >> 1;
        return max(
            get(id << 1, l, mid, lef, rig),
            get(id << 1 | 1, mid + 1, r, lef, rig)
        );
    }

    int get(int l, int r) {
        return get(1, 1, n, l, r);
    }
} ST;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
        //freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif
    
    cin >> n >> d;

    memset(a, -1, sizeof a);
    memset(sp, -1, sizeof sp);
    memset(sp2, -1, sizeof sp2);

    for (int i = 1; i <= n; i ++)
        cin >> a[i], sp[0][i] = a[i], b[i] = {a[i], i};

    for (int i = 1; i < 20; i ++)
        for (int j = 1; j + (1 << i) - 1 <= n; j ++)
            sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << i - 1)]);

    auto getA = [&] (int l, int r) {
        int k = log2(r - l + 1);
        return min(sp[k][l], sp[k][r - (1 << k) + 1]);
    };

    for (int i = 1; i <= n; i ++)
        sp2[0][i] = getA(i, i + d - 1);
    
    for (int i = 1; i < 20; i ++)
        for (int j = 1; j + (1 << i) - 1 <= n; j ++)
            sp2[i][j] = max(sp2[i - 1][j], sp2[i - 1][j + (1 << i - 1)]);

    auto get = [&] (int l, int r) {
        int k = log2(r - l + 1);
        return max(sp2[k][l], sp2[k][r - (1 << k) + 1]);
    };

    for (int i = 1; i <= n; i ++) {
        int ori = max(1, i - d);
        L[i] = ori; R[i] = i;
        int l = 1, r = ori;
        while (l <= r) {
            int mid = l + r >> 1;
            if (get(mid, ori) < a[i])
                L[i] = mid, r = mid - 1;
            else    
                l = mid + 1;
        }
    }

    ST.init();

    ll ans = 0;

    b[n + 1] = {-1, 0};
    sort(b + 1, b + 1 + n);

    for (int i = 1; i <= n; i ++) {
        int l = i;
        while (b[l + 1].st == b[i].st) l ++;

        /// solve
        for (int j = i; j <= l; j ++) {
            int id = b[j].nd;
            ll cur = ST.get(L[id], R[id]) + 1;
            save[j] = cur;

            ans = max(ans, cur);         
        }

        /// update
        for (int j = i; j <= l; j ++) {
            int id = b[j].nd;
            ST.upd(id, save[j]);
        }

        /// end
        i = l;
    }

    cout << ans << '\n';

    return 0;
}    
/**  /\_/\
*   (= ._.)
*   / >🍵 \>🍮
**/

Compilation message (stderr)

Main.cpp:136:9: warning: "/*" within comment [-Wcomment]
  136 | /**  /\_/\
      |          
Main.cpp: In member function 'void segment::upd(int, int, int, int, int)':
Main.cpp:28:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'int segment::get(int, int, int, int, int)':
Main.cpp:40:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:70:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   70 |             sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << i - 1)]);
      |                                                              ~~^~~
Main.cpp:82:67: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   82 |             sp2[i][j] = max(sp2[i - 1][j], sp2[i - 1][j + (1 << i - 1)]);
      |                                                                 ~~^~~
Main.cpp:94:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |             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