oj.uz

Submission #846856

# Submission time Handle Problem Language Result Execution time Memory
846856 2023-09-08T14:30:16 Z Abito Financial Report (JOI21_financial) C++17
17 / 100
 470 ms 21696 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 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 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 2396 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Incorrect 1 ms 2392 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 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 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 2396 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Incorrect 1 ms 2392 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 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 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 2396 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Incorrect 1 ms 2392 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 34 ms 8704 KB Output is correct
2 Correct 32 ms 7592 KB Output is correct
3 Correct 33 ms 7456 KB Output is correct
4 Correct 33 ms 7516 KB Output is correct
5 Correct 32 ms 7516 KB Output is correct
6 Correct 33 ms 7512 KB Output is correct
7 Correct 45 ms 3420 KB Output is correct
8 Correct 29 ms 8784 KB Output is correct
9 Correct 42 ms 7508 KB Output is correct
10 Correct 34 ms 8028 KB Output is correct
11 Correct 32 ms 7504 KB Output is correct
12 Correct 33 ms 7516 KB Output is correct
13 Correct 29 ms 7476 KB Output is correct
14 Correct 29 ms 7504 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 7512 KB Output is correct
2 Correct 83 ms 5596 KB Output is correct
3 Correct 132 ms 5792 KB Output is correct
4 Correct 470 ms 21584 KB Output is correct
5 Correct 317 ms 21572 KB Output is correct
6 Correct 458 ms 21572 KB Output is correct
7 Correct 174 ms 21696 KB Output is correct
8 Correct 177 ms 21332 KB Output is correct
9 Correct 163 ms 21612 KB Output is correct
10 Correct 245 ms 21440 KB Output is correct
11 Correct 371 ms 21328 KB Output is correct
12 Correct 325 ms 21332 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 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 2396 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Incorrect 1 ms 2392 KB Output isn't correct
17 Halted 0 ms 0 KB -