제출 #1305250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305250		nekolie	Financial Report (JOI21_financial)	C++20	100 / 100	1222 ms	84392 KiB

Main

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

const int baza = (1<<19), M = 300007;
map<int,int> mp; set<pair<int,int>> s;
int n,k, a[M], dp[M], d[2*baza];
multiset<int> kiki[M]; vector<int> ind[M], take[M];
void akt(int i) {
    i = (i+baza)/2;
    while (i > 0)
        d[i] = max(d[2*i],d[2*i+1]), i >>= 1;
}
int maks(int l, int r) {
    l += baza-1, r += baza+1; int w = 0;
    while (l/2 != r/2) {
        if ((l&1) == 0)
            w = max(w,d[l+1]);
        if ((r&1) == 1)
            w = max(w,d[r-1]);
        l >>= 1, r >>= 1;
    }
    return w;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i], mp[a[i]] = 0;
    int cnt = 1; s.insert({0,n-1});
    for (auto it = mp.begin(); it != mp.end(); it++)
        mp[it->first] = cnt++;
    for (int i = 0; i < n; i++)
        a[i] = mp[a[i]], ind[a[i]].push_back(i);
    for (int x = 1; x <= n; x++) {
        /*
        cerr << "MANY MANY CHEATING " << x << endl;
        for (auto [l,r] : s)
            cerr << l << " " << r << endl;
        */
        kiki[x].insert(0);
        for (int i : ind[x]) {
            if (s.empty() || (*s.rbegin()).second < i)
                continue;
            auto it = ((i >= (*s.rbegin()).first) ? prev(s.end()) : prev(s.upper_bound({i,n+1})));
            if ((*it).second >= i && i >= (*it).first) {
                int l = (*it).first, r = (*it).second;
                //cerr << i << " " << l << " " << r << endl;
                s.erase(it);
                if (i-l >= k)
                    s.insert({l,i-1});
                if (r-i >= k)
                    s.insert({i+1,r});
            }
        }
        for (int i : ind[x]) {
            if (!s.empty() && (*s.rbegin()).second > i) {
                int lim = (*s.upper_bound({i,-1})).first+k;
                //cerr << i << " " << lim << endl;
                take[lim].push_back(i);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j : take[i])
            kiki[a[j]].erase(kiki[a[j]].find(dp[j])), d[a[j]+baza] = *kiki[a[j]].rbegin(), akt(a[j]);
        dp[i] = 1 + maks(0,a[i]-1), kiki[a[i]].insert(dp[i]), d[a[i]+baza] = *kiki[a[i]].rbegin(), akt(a[i]);
        //cerr << i << " " << dp[i] << endl;
    }
    cout << *max_element(dp,dp+n) << endl;
    return 0;
}

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