제출 #1085248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1085248		sunflower	Financial Report (JOI21_financial)	C++14	0 / 100	1 ms	604 KiB

Main

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

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define sz(x) ((int) (x).size())
#define all(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

int n, d;

const int maxn = (int) 100 + 2;
const int LOG = 18;

int a[maxn + 2], dp[maxn + 2];
int st[maxn + 2][LOG + 1];
int f[maxn + 2][LOG + 1];
int minPos[maxn + 2];
vector <int> tree[4 * maxn + 7];
int seg[4 * maxn + 7];

// ----------- SEGMENT TREE ---------------------- //
    void update(int pos, int v) {
        int id = 1, l = 1, r = n;
        while (l < r) {
            int g = (l + r) >> 1;
            if (g >= pos) {
                id = 2 * id;
                r = g;
            } else {
                id = 2 * id + 1;
                l = g + 1;
            }
        }

        maximize(seg[id], v);

        while (id > 1) {
            id >>= 1;
            seg[id] = max(seg[id << 1], seg[id << 1 | 1]);
        }
    }

    int get(int id, int l, int r, int u, int v) {
        if (l > v || u > r) return 0;
        if (u <= l && r <= v) return seg[id];
        int g = (l + r) >> 1;
        return max(get(id << 1, l, g, u, v), get(id << 1 | 1, g + 1, r, u, v));
    }
// ----------- SEGMENT TREE ---------------------- //

namespace subtask6 {

    void prepare() {
        FOR(i, 1, n) st[i][0] = a[i];

        FOR(j, 1, LOG)
            FOR(i, 1, n - MASK(j) + 1)
                st[i][j] = min(st[i][j - 1], st[i + MASK(j - 1)][j - 1]);
    }

    int getmin(int l, int r) {
        int k = __lg(r - l + 1);
        return min(st[l][k], st[r - MASK(k) + 1][k]);
    }

    void process() {
        FOR(j, 1, LOG)
            for (int i = 1; i <= n; ++i) {
                st[i][j] = st[st[i][j - 1]][j - 1];
                f[i][j] = max(f[i][j - 1], f[st[i][j - 1]][j - 1]);
            }
    }

    int findPos(int i) {
        int val = a[i];
        for (int j = LOG; j >= 0; --j) {
            if (f[i][j] < val && f[i][j] > 0) {
                i = st[i][j];
            }
        }

        return i;
    }

    #define vi vector <int>

    vi mer(vi &x, vi &y) {
        vi res;
        int i = 0, j = 0;
        while (i < sz(x) && j < sz(y)) {
            if (x[i] <= y[j]) res.push_back(x[i++]);
            else res.push_back(y[j++]);
        }

        while (i < sz(x)) res.push_back(x[i++]);
        while (j < sz(y)) res.push_back(y[j++]);

        return res;
    }

    void updateINC(int pos, int val) {
        int id = 1, l = 1, r = n;
        while (l < r) {
            int g = (l + r) >> 1;
            if (g >= pos) {
                id = 2 * id;
                r = g;
            } else {
                id = 2 * id + 1;
                l = g + 1;
            }
        }
        tree[id].push_back(val);
        while (id > 1) {
            id >>= 1;
            tree[id] = mer(tree[id << 1], tree[id << 1 | 1]);
        }
    }

    int GET(int id, int l, int r, int u, int v, int x) {
        if (l > v || u > r) return 0;
        if (u <= l && r <= v) {
            int lo = 0, hi = sz(tree[id]) - 1, m, vt = -1;
            while (lo <= hi) {
                m = (lo + hi) >> 1;
                if (tree[id][m] < x) vt = m, lo = m + 1;
                else hi = m - 1;
            }
            return (~vt ? tree[id][vt] : 0);
        }

        int g = (l + r) >> 1;
        return max(GET(id << 1, l, g, u, v, x), GET(id << 1 | 1, g + 1, r, u, v, x));
    }

    void solve() {
        prepare();
        FOR(i, 2, n) {
            int l = max(1, i - d), r = i - 1, g, vt = -1;
            int x = getmin(l, r);
            while (l <= r) {
                g = (l + r) >> 1;
                if (getmin(g, i - 1) > x) r = g - 1;
                else vt = g, l = g + 1;
            }

            minPos[i] = vt;
        }
        minPos[1] = 1;
        FOR(i, 1, n) st[i][0] = minPos[i], f[i][0] = a[minPos[i]];
        process();

        FOR(i, 1, n) minPos[i] = findPos(i);
        prepare();

        FOR(i, 1, n) {
            dp[i] = 1;
            int j = minPos[i];
            if (j != i) {
                int x = GET(1, 1, n, j, i - 1, a[i]);
                int y = getmin(j, i - 1);
                dp[i] = get(1, 1, n, y, x) + 1;
            }
            update(a[i], dp[i]);
            updateINC(i, a[i]);
        }

//        cout << *max_element(dp + 1, dp + 1 + n);
        FOR(i, 1, n) cout << a[i] << " " << dp[i] << "\n";
    }
};

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> d;
    vector <int> v;
    FOR(i, 1, n) cin >> a[i], v.push_back(a[i]);
    sort(all(v));
    v.erase(unique(all(v)), v.end());

    FOR(i, 1, n) a[i] = lower_bound(all(v), a[i]) - v.begin() + 1;

    subtask6 :: solve();

    return 0;
}

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