Submission #424386

#	Time	Username	Problem	Language	Result	Execution time	Memory
424386		Osama_Alkhodairy	Financial Report (JOI21_financial)	C++17	100 / 100	343 ms	12100 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 300001;

int n, d, tree[2 * N];
vector <int> a;

void update(int p, int v){
    for(tree[p += n] = v ; p > 1 ; p >>= 1){
        tree[p >> 1] = max(tree[p], tree[p ^ 1]);
    }
}
int query(int l, int r){
    r++;
    int ret = 0;
    for(l += n, r += n ; l < r ; l >>= 1, r >>= 1){
        if(l & 1) ret = max(ret, tree[l++]);
        if(r & 1) ret = max(ret, tree[--r]);
    }
    return ret;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> d;
    a.resize(n);
    for(auto &i : a) cin >> i;
    vector <pair <int, int> > all;
    for(int i = 0 ; i < n ; i++){
        all.push_back(make_pair(a[i], i));
    }
    sort(all.begin(), all.end(), [&](pair <int, int> &l, pair <int, int> &r){
        return make_pair(l.first, -l.second) < make_pair(r.first, -r.second);
    });
    set <pair <int, int> > s;
    vector <int> f(n);
    for(auto &i : all){
        int idx = i.second;
        auto cur = make_pair(idx, idx);
        auto it = s.lower_bound(make_pair(idx, -1));
        vector <pair <int, int> > to_erase;
        if(it != s.end() && idx + d >= it->first){
            cur.second = it->second;
            to_erase.push_back(*it);
        }
        if(it != s.begin()){
            it--;
            if(idx - d <= it->second){
                cur.first = it->first;
                cur.second = max(cur.second, it->second);
                to_erase.push_back(*it);
            }
        }
        for(auto &j : to_erase){
            s.erase(j);
        }
        f[idx] = min(cur.second + d, n - 1);
        s.insert(cur);
    }
    vector <int> dp(n);
    sort(all.begin(), all.end(), [&](pair <int, int> &l, pair <int, int> &r){
        return make_pair(-l.first, l.second) < make_pair(-r.first, r.second);
    });
    for(auto &i : all){
        int idx = i.second;
        dp[idx] = query(idx, f[idx]) + 1;
        update(idx, dp[idx]);
    }
    int ans = 0;
    for(auto &i : dp) ans = max(ans, i);
    cout << ans << endl;
}

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