Submission #763114

#	Time	Username	Problem	Language	Result	Execution time	Memory
763114		khanhphucscratch	Financial Report (JOI21_financial)	C++14	0 / 100	236 ms	136924 KiB

Main

#include<bits/stdc++.h>
using namespace std;
unordered_map<int, int> dic;
deque<pair<int, int>> b[200001];
int st[800005], a[200001], dp[200001];
void add(int node, int l, int r, int p, int np, int v)
{
    if(l > p || r < p) return;
    if(l == p && r == p){
        while(b[l].size() > 0 && b[l].back().first <= v) b[l].pop_back();
        b[l].push_back({v, np});
        st[node] = b[l].front().first;
    }
    else{
        add(node*2, l, (l+r)/2, p, np, v);
        add(node*2+1, (l+r)/2+1, r, p, np, v);
        st[node] = max(st[node*2], st[node*2+1]);
    }
}
void del(int node, int l, int r, int p, int np)
{
    if(l > p || r < p) return;
    if(l == p && r == p){
        while(b[l].size() > 0 && b[l].front().second <= np) b[l].pop_front();
        if(b[l].size() > 0) st[node] = b[l].front().first;
        else st[node] = 0;
    }
    else{
        del(node*2, l, (l+r)/2, p, np);
        del(node*2+1, (l+r)/2+1, r, p, np);
        st[node] = max(st[node*2], st[node*2+1]);
    }
}
int query(int node, int l, int r, int tl, int tr)
{
    if(l > tr || r < tl) return -1e9;
    else if(l >= tl && r <= tr) return st[node];
    else return max(query(node*2, l, (l+r)/2, tl, tr), query(node*2+1, (l+r)/2+1, r, tl ,tr));
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, d;
    cin>>n>>d;
    set<int> f;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
        f.insert(a[i]);
    }
    f.insert(0);
    int c = 0;
    for(int i : f) dic[i] = ++c;
    for(int i = 1; i <= n; i++){
        if(dic[a[i]] > 1) dp[i] = query(1, 1, n, 1, dic[a[i]]-1) + 1;
        else dp[i] = 1;
        add(1, 1, n, dic[a[i]], i, dp[i]);
        if(i-d > 0) del(1, 1, n, dic[a[i-d]], i-d);
        //cout<<dp[i]<<" "<<dic[a[i]]<<" "<<query(1, 1, n,1, 2)<<endl;
    }
    int ans = 0;
    for(int i = n; i >= n-d; i--) ans = max(ans, dp[i]);
    cout<<ans;
}

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