oj.uz

Submission #967702

# Submission time Handle Problem Language Result Execution time Memory
967702 2024-04-22T16:22:57 Z vjudge1 Financial Report (JOI21_financial) C++17
5 / 100
 175 ms 17232 KB 
#include <bits/stdc++.h>
#define getbit(i, j) ((i >> j) & 1)
#define maxn 300005
#define name "main"
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

long long GetRandom(long long l, long long r)
{
    return uniform_int_distribution<long long> (l, r)(rng);
}

int n,d,a[maxn],st[maxn*4],dp[maxn],dem[maxn],sl,res,lazy[maxn*4],dd[maxn],mod=-1e9;
pair<int,int> b[maxn];

void build(int id,int l,int r)
{
    if(l>r) return;
    if(l==r)
    {
        st[id]=mod;
        return;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    st[id]=-1e9;
}

void lazy1(int id)
{
    int val=lazy[id];
    lazy[id]=0;
    lazy[id*2]+=val;
    lazy[id*2+1]+=val;
    st[id*2]+=val;
    st[id*2+1]+=val;
    return;
}

void updategt(int id,int l,int r,int d,int c,int val)
{
    if(l>c||r<d) return;
    if(l>=d&&r<=c)
    {
        st[id]+=val;
        lazy[id]+=val;
        return;
    }
    int mid=(l+r)/2;
    lazy1(id);
    updategt(id*2,l,mid,d,c,val);
    updategt(id*2+1,mid+1,r,d,c,val);
    st[id]=max(st[id*2],st[id*2+1]);
}

void updatema(int id,int l,int r,int vt,int val)
{
    if(l>vt||r<vt) return;
    if(l==r)
    {
        st[id]=max(st[id],val);
        return;
    }
    int mid=(l+r)/2;
    lazy1(id);
    updatema(id*2,l,mid,vt,val);
    updatema(id*2+1,mid+1,r,vt,val);
    st[id]=max(st[id*2],st[id*2+1]);
}

int get(int id,int l,int r,int d,int c)
{
    if(l>c||r<d) return 0;
    if(l>=d&&r<=c) return st[id];
    int mid=(l+r)/2;
    lazy1(id);
    return max(get(id*2,l,mid,d,c),get(id*2+1,mid+1,r,d,c));
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
//    if(fopen(name".inp","r"))
//    {
//        freopen(name".inp","r",stdin);
//        freopen(name".out","w",stdout);
//    }
    cin >> n >> d;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        b[i]={a[i],i};
    }
    sort(b+1,b+n+1);
    sl=1;
    a[b[1].second]=sl;
    for(int i=2;i<=n;i++)
    {
        if(b[i].first>b[i-1].first) sl++;
        a[b[i].second]=sl;
    }

    build(1,1,sl);
    int vt=1;
    for(int i=1;i<=n;i++)
    {
        while(vt<i-d)
        {
            if(dd[a[vt]]==vt)
            {
                updategt(1,1,sl,a[vt],a[vt],mod);
            }
            vt++;
        }
        int val=get(1,1,sl,1,a[i]-1);
        dp[i]=max(dp[i],val+1);
//        cout<<i<<' '<<dp[i]<<'\n';
        res=max(res,dp[i]);
        updatema(1,1,sl,a[i],dp[i]);
//        if(i==5) cout<<get(1,1,sl,3,3)<<' '<<a[i]<<'\n';
        dd[a[i]]=i;
    }
    cout<<res;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12624 KB Output is correct
2 Incorrect 72 ms 12424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 12624 KB Output is correct
2 Correct 87 ms 12804 KB Output is correct
3 Correct 121 ms 12804 KB Output is correct
4 Correct 173 ms 16900 KB Output is correct
5 Correct 162 ms 16900 KB Output is correct
6 Correct 164 ms 16900 KB Output is correct
7 Correct 118 ms 17232 KB Output is correct
8 Correct 156 ms 16980 KB Output is correct
9 Correct 126 ms 16888 KB Output is correct
10 Correct 161 ms 17096 KB Output is correct
11 Correct 175 ms 16956 KB Output is correct
12 Correct 156 ms 17072 KB Output is correct

Subtask #6
0 / 35.0

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