oj.uz

Submission #846853

# Submission time Handle Problem Language Result Execution time Memory
846853 2023-09-08T14:26:10 Z Abito Financial Report (JOI21_financial) C++17
17 / 100
 474 ms 21808 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
//#define int long long
#define y1 YONE
typedef unsigned long long ull;
using namespace std;
const int N=3e5+5;
int a[N],n,d,bit[N],seg[4*N+5],b[N],dp[N];
void upd(int x){
    while (x<=n){
        bit[x]++;
        x+=x&-x;
    }return;
}int calc(int x){
    int y=0;
    while (x){
        y+=bit[x];
        x-=x&-x;
    }return y;
}
int edit(int node,int l,int r,int idx,int val){
    if (l==r) return seg[node]=val;
    int mid=(l+r)/2;
    if (idx<=mid) return seg[node]=max(edit(node*2,l,mid,idx,val),seg[node*2+1]);
    return seg[node]=max(edit(node*2+1,mid+1,r,idx,val),seg[node*2]);
}
int query(int node,int l,int r,int lx,int rx){
    if (r<lx || l>rx) return 0;
    if (l>=lx && r<=rx) return seg[node];
    int mid=(l+r)/2;
    return max(query(node*2,l,mid,lx,rx),query(node*2+1,mid+1,r,lx,rx));
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>d;
    for (int i=1;i<=n;i++) cin>>a[i];
    a[0]=INT_MIN;
    if (d==1){
        stack<int> s;
        for (int i=1;i<=n;i++){
            while (!s.empty()){
                if (a[s.top()]<a[i]) s.pop();
                else{
                    b[i]=s.top();
                    break;
                }
            }s.push(i);
        }
        int ans=0;
        for (int i=n;i;i--){
            upd(b[i]+1);
            ans=max(ans,calc(i));
        }cout<<ans<<endl;
        return 0;
    }
    if (d==n){
        map<int,int> mp;mp[INT_MIN]++;
        for (int i=1;i<=n;i++) mp[a[i]]++;
        int c=0;
        for (auto u:mp) mp[u.F]=c++;
        for (int i=1;i<=n;i++){
            a[i]=mp[a[i]];
            edit(1,1,n,a[i],query(1,1,n,0,a[i]-1)+1);
        }cout<<query(1,1,n,0,4*N+4)<<endl;
        return 0;
    }int ans=0;
    for (int i=1;i<=n;i++){
        dp[i]=1;
        for (int j=max(i-d,1);j<i;j++) if (a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1);
        ans=max(ans,dp[i]);
    }cout<<ans<<endl;
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Incorrect 1 ms 2396 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Incorrect 1 ms 2396 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Incorrect 1 ms 2396 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8784 KB Output is correct
2 Correct 32 ms 7764 KB Output is correct
3 Correct 34 ms 7504 KB Output is correct
4 Correct 33 ms 7508 KB Output is correct
5 Correct 33 ms 7504 KB Output is correct
6 Correct 33 ms 7540 KB Output is correct
7 Correct 44 ms 3408 KB Output is correct
8 Correct 28 ms 8652 KB Output is correct
9 Correct 45 ms 7516 KB Output is correct
10 Correct 31 ms 8024 KB Output is correct
11 Correct 35 ms 7508 KB Output is correct
12 Correct 33 ms 7504 KB Output is correct
13 Correct 29 ms 7512 KB Output is correct
14 Correct 29 ms 7448 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 8016 KB Output is correct
2 Correct 82 ms 5456 KB Output is correct
3 Correct 129 ms 5712 KB Output is correct
4 Correct 461 ms 21476 KB Output is correct
5 Correct 373 ms 21808 KB Output is correct
6 Correct 474 ms 21380 KB Output is correct
7 Correct 181 ms 21584 KB Output is correct
8 Correct 186 ms 21584 KB Output is correct
9 Correct 157 ms 21328 KB Output is correct
10 Correct 247 ms 21376 KB Output is correct
11 Correct 345 ms 21328 KB Output is correct
12 Correct 308 ms 21628 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Incorrect 1 ms 2396 KB Output isn't correct
17 Halted 0 ms 0 KB -