oj.uz

Submission #967653

# Submission time Handle Problem Language Result Execution time Memory
967653 2024-04-22T15:13:52 Z vjudge1 Financial Report (JOI21_financial) C++17
5 / 100
 148 ms 13992 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;
pair<int,int> b[maxn];

void update(int id,int l,int r,int vt,int val)
{
    if(l>vt||r<vt) return;
    if(l==r)
    {
        st[id]=val;
        return;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,vt,val);
    update(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;
    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;
    }
    int vt=1;
    for(int i=1;i<=n;i++)
    {
        while(vt<i-d)
        {
            dem[a[vt]]--;
            if(dem[a[vt]]==0) update(1,1,sl,a[vt],0);
            vt++;
        }
        dp[i]=get(1,1,sl,1,a[i]-1)+1;
        dem[a[i]]++;
        res=max(res,dp[i]);
        update(1,1,sl,a[i],dp[i]);
    }
    cout<<res;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6604 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 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 4444 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Incorrect 1 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 1 ms 6492 KB Output is correct
2 Correct 1 ms 6604 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 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 4444 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Incorrect 1 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 1 ms 6492 KB Output is correct
2 Correct 1 ms 6604 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 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 4444 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Incorrect 1 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 30 ms 11856 KB Output is correct
2 Incorrect 67 ms 9812 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 31 ms 12112 KB Output is correct
2 Correct 85 ms 10196 KB Output is correct
3 Correct 115 ms 10068 KB Output is correct
4 Correct 148 ms 13908 KB Output is correct
5 Correct 138 ms 13756 KB Output is correct
6 Correct 145 ms 13676 KB Output is correct
7 Correct 95 ms 13992 KB Output is correct
8 Correct 106 ms 13936 KB Output is correct
9 Correct 108 ms 13656 KB Output is correct
10 Correct 133 ms 13908 KB Output is correct
11 Correct 139 ms 13752 KB Output is correct
12 Correct 131 ms 13908 KB Output is correct

Subtask #6
0 / 35.0

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