oj.uz

Submission #763114

# Submission time Handle Problem Language Result Execution time Memory
763114 2023-06-22T04:03:54 Z khanhphucscratch Financial Report (JOI21_financial) C++14
0 / 100
 236 ms 136924 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 134836 KB Output is correct
2 Correct 67 ms 134948 KB Output is correct
3 Correct 74 ms 134940 KB Output is correct
4 Correct 67 ms 134836 KB Output is correct
5 Correct 67 ms 134952 KB Output is correct
6 Correct 66 ms 134948 KB Output is correct
7 Correct 67 ms 134860 KB Output is correct
8 Correct 68 ms 134876 KB Output is correct
9 Correct 69 ms 134896 KB Output is correct
10 Correct 69 ms 134924 KB Output is correct
11 Correct 68 ms 134916 KB Output is correct
12 Correct 68 ms 134872 KB Output is correct
13 Correct 80 ms 134836 KB Output is correct
14 Correct 80 ms 134856 KB Output is correct
15 Incorrect 69 ms 134860 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 134836 KB Output is correct
2 Correct 67 ms 134948 KB Output is correct
3 Correct 74 ms 134940 KB Output is correct
4 Correct 67 ms 134836 KB Output is correct
5 Correct 67 ms 134952 KB Output is correct
6 Correct 66 ms 134948 KB Output is correct
7 Correct 67 ms 134860 KB Output is correct
8 Correct 68 ms 134876 KB Output is correct
9 Correct 69 ms 134896 KB Output is correct
10 Correct 69 ms 134924 KB Output is correct
11 Correct 68 ms 134916 KB Output is correct
12 Correct 68 ms 134872 KB Output is correct
13 Correct 80 ms 134836 KB Output is correct
14 Correct 80 ms 134856 KB Output is correct
15 Incorrect 69 ms 134860 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 134836 KB Output is correct
2 Correct 67 ms 134948 KB Output is correct
3 Correct 74 ms 134940 KB Output is correct
4 Correct 67 ms 134836 KB Output is correct
5 Correct 67 ms 134952 KB Output is correct
6 Correct 66 ms 134948 KB Output is correct
7 Correct 67 ms 134860 KB Output is correct
8 Correct 68 ms 134876 KB Output is correct
9 Correct 69 ms 134896 KB Output is correct
10 Correct 69 ms 134924 KB Output is correct
11 Correct 68 ms 134916 KB Output is correct
12 Correct 68 ms 134872 KB Output is correct
13 Correct 80 ms 134836 KB Output is correct
14 Correct 80 ms 134856 KB Output is correct
15 Incorrect 69 ms 134860 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 136924 KB Output is correct
2 Incorrect 198 ms 136904 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 136912 KB Output is correct
2 Incorrect 170 ms 136860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 134836 KB Output is correct
2 Correct 67 ms 134948 KB Output is correct
3 Correct 74 ms 134940 KB Output is correct
4 Correct 67 ms 134836 KB Output is correct
5 Correct 67 ms 134952 KB Output is correct
6 Correct 66 ms 134948 KB Output is correct
7 Correct 67 ms 134860 KB Output is correct
8 Correct 68 ms 134876 KB Output is correct
9 Correct 69 ms 134896 KB Output is correct
10 Correct 69 ms 134924 KB Output is correct
11 Correct 68 ms 134916 KB Output is correct
12 Correct 68 ms 134872 KB Output is correct
13 Correct 80 ms 134836 KB Output is correct
14 Correct 80 ms 134856 KB Output is correct
15 Incorrect 69 ms 134860 KB Output isn't correct
16 Halted 0 ms 0 KB -