Submission #940341

#	Time	Username	Problem	Language	Result	Execution time	Memory
940341		haxorman	Financial Report (JOI21_financial)	C++14	100 / 100	763 ms	63680 KiB

Main

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

#define int long long

const int mxN = 3e5 + 7;
const int SZ = exp2(ceil(log2(mxN)));
const int INF = 1e9 + 7;

int n, d, arr[mxN], seg[4*mxN], dp[mxN], dsu[mxN], lb[mxN];
bool done[mxN];
set<int> inds;
vector<int> pos[mxN];

int find(int x) {
    return dsu[x] < 0 ? x : dsu[x] = find(dsu[x]);
}

void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;

    if (dsu[x] > dsu[y]) {
        swap(x, y);
    }
    dsu[x] += dsu[y];
    dsu[y] = x;
    
    inds.erase(lb[x]);
    inds.erase(lb[y]);
    lb[x] = min(lb[x], lb[y]);

    if (-dsu[x] >= d) {
        inds.insert(lb[x]);
    }
}

void update(int ind, int val) {
    seg[ind+=SZ] = val;
    while (ind /= 2) {
        seg[ind] = max(seg[2*ind], seg[2*ind+1]);
    }
}

int query(int lo, int hi, int ind = 1, int l = 0, int r = SZ - 1) {
    if (lo > r || l > hi) {
        return -INF;
    }

    if (lo <= l && r <= hi) {
        return seg[ind];
    }

    int mid = (l+r)/2;
    return max(query(lo,hi,2*ind,l,mid), query(lo,hi,2*ind+1,mid+1,r));
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> d;
    
    vector<int> vec;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        vec.push_back(arr[i]);
    }
    sort(vec.begin(), vec.end());
    
    int val = 1;
    map<int,int> conv;
    for (int i = 0; i < n; ++i) {
        if (conv.find(vec[i]) == conv.end()) {
            conv[vec[i]] = val++;
        }
    }
    
    vec.clear();
    for (int i = 0; i < n; ++i) {
        arr[i] = conv[arr[i]];

        if (pos[arr[i]].empty()) {
            vec.push_back(arr[i]);
        }
        pos[arr[i]].push_back(i);
        lb[i] = i;

        if (i < n-1) {
            update(i, -INF);
        }
    }
    sort(vec.begin(), vec.end());
    
    inds.insert(n);
    memset(dsu, -1, sizeof(dsu));
    for (int i = vec.size()-1; i >= 0; --i) {
        for (auto x : pos[vec[i]]) {
            int to = *inds.upper_bound(x);
            dp[x] = query(x, min(n-1, to+d-1)) + 1;
        }

        for (auto x : pos[vec[i]]) {
            update(x, dp[x]);

            done[x] = true;
            if (d == 1) {
                inds.insert(x);
            }

            if (done[x+1]) {
                unite(x,x+1);
            }
            if (x && done[x-1]) {
                unite(x,x-1);
            }
        }
    }
    
    /*
    for (int i = 0; i < n; ++i) {
        cout << query(i,i) << ' ';
    }
    cout << "\n";
    */

    cout << query(0, n-1) << "\n";
}

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