Submission #1218796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218796		CodeLakVN	Financial Report (JOI21_financial)	C++20	100 / 100	500 ms	25088 KiB

Main

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

#define task "main"
#define no "NO"
#define yes "YES"
#define F first
#define S second
#define vec vector
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)

const int MAX_N = (int)3e5 + 5;

int n, d;
int a[MAX_N];

namespace sub1 {
    void solve() {
        int ans = 0;
        FOR(mask, 0, (1 << n) - 1) {
            int cur = 0, maxx = 0, prev = n + 1;
            FOR(i, 0, n - 1) {
                if ((mask >> i) & 1) {
                    if (i + 1 - prev > d) {
                        cur = -1;
                        break;
                    }
                    if (a[i + 1] > maxx) {
                        cur++;
                        maxx = a[i + 1];
                    } 
                    prev = i + 1;
                }
            } 
            ans = max(ans, cur);
        }

        cout << ans << "\n";
    }
}

namespace subFull {
    int minPos[MAX_N];

    struct DSU {
        vector<int> par;
    
        DSU(int _n) {
            par.resize(_n + 1);
            FOR(i, 1, _n) par[i] = i, minPos[i] = i;
        }

        int getP(int a) {
            return (a == par[a] ? a : par[a] = getP(par[a]));
        }

        void unite(int u, int v) {
            u = getP(u), v = getP(v);
            if (u == v) return;
            minPos[u] = min(minPos[u], minPos[v]);
            par[v] = u;
        }
    };

    struct IT {
        int tree[4 * MAX_N];
        int n;

        void init(int _n) {
            n = _n;
            memset(tree, -0x3f, sizeof(tree));
        }

        void update(int id, int l, int r, int pos, int val) {
            if (l == r) {
                tree[id] = max(tree[id], val);
                return;
            }
            int mid = (l + r) >> 1;
            if (pos <= mid) update(2 * id, l, mid, pos, val);
            else update(2 * id + 1, mid + 1, r, pos, val);
            tree[id] = max(tree[2 * id], tree[2 * id + 1]);
        }

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

        void update(int pos, int val) { update(1, 1, n, pos, val); }

        int get(int u, int v) { return get(1, 1, n, u, v); }
    } st;

    ii b[MAX_N];

    void solve() {
        FOR(i, 1, n) b[i] = {a[i], -i};
        sort(b + 1, b + n + 1);
        
        set<int> s;
        st.init(n);

        DSU dsu(n);

        FOR(i, 1, n) {
            int pos = -b[i].S;
            auto it = s.upper_bound(pos);
            if (it != s.end() && *it - pos <= d) dsu.unite(*it, pos);
            if (it != s.begin()) {
                it--;
                if (pos - *it <= d) dsu.unite(*it, pos);
            }
            s.insert(pos);

            int f = max(0, st.get(minPos[dsu.getP(pos)], pos - 1) + 1);
            st.update(pos, f);
        }

        cout << st.get(1, n) << "\n";
    }
}

void solve() {
    cin >> n >> d;
    FOR(i, 1, n) cin >> a[i];

    subFull::solve();
}

int32_t main() {
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    bool multitest = 0;
    int numTest = 1;
    if (multitest) cin >> numTest;

    while (numTest--) {
        solve();
    }

    return 0;
}

/* Lak lu theo dieu nhac!!!! */

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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