oj.uz

Submission #423510

# Submission time Handle Problem Language Result Execution time Memory
423510 2021-06-11T08:20:49 Z 장태환(#7573) Financial Report (JOI21_financial) C++17
5 / 100
 543 ms 16392 KB 
#include <bits/stdc++.h>
using namespace std;
struct stree
{
    int st[600100];
    int N;
    void init(vector<int>arr)
    {
        N=arr.size();
        int i;
        for(i=0;i<N;i++)
            st[i+N]=arr[i];
        for(i=N-1;i>0;i--)
            st[i]=max(st[i<<1],st[i<<1|1]);
    }
    void upd(int n,int k)
    {
        st[N+n]=k;
        for(n+=N;n>1;n>>=1)
        {
            st[n>>1]=max(st[n],st[n^1]);
        }
    }
    int q(int l,int r,int mi)
    {
        int ans=mi;
        l+=N;
        r+=N;
        for(;l<r;l>>=1,r>>=1)
        {
            if(l&1)
                ans=max(ans,st[l++]);
            if(r&1)
                ans=max(ans,st[--r]);

        }
        return ans;
    }
}val,cma,dp;
string s[3];
int lim[300100];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N,M;
    cin >> N >> M;
    int i;
    vector<pair<int,int>>x;
    vector<int>arr;
    vector<int>da(N,0);
    dp.init(da);
    for(i=0;i<N;i++)
    {
        int a;
        cin >> a;
        x.push_back({-a,i});
        arr.push_back(-a);
    }
    sort(x.begin(),x.end());
    val.init(arr);
    vector<int>su;
    for(i=0;i<N-M;i++)
    {
        su.push_back(-val.q(i,i+M+1,-(1<<30)));
    }
    cma.init(su);
    for(i=0;i<N;i++)
    {
        int s=i+1;
        int e=su.size();
        while(s<e)
        {
            int m=(s+e)>>1;
            if(cma.q(i+1,m+1,0)<=-arr[i])
                s=m+1;
            else
                e=m;
        }
        if(e==su.size())
            lim[i]=N;
        lim[i]=e+M+1;
    }
    int ans=0;
    for(i=0;i<N;i++)
    {
        int va=dp.q(x[i].second+1,lim[x[i].second],0)+1;
        ans=max(ans,va);
        dp.upd(x[i].second,va);
    }
    cout << ans;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:80:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         if(e==su.size())
      |            ~^~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 16360 KB Output is correct
2 Correct 470 ms 16360 KB Output is correct
3 Incorrect 477 ms 16392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 12916 KB Output is correct
2 Correct 128 ms 12928 KB Output is correct
3 Correct 129 ms 12824 KB Output is correct
4 Correct 134 ms 12860 KB Output is correct
5 Correct 138 ms 12848 KB Output is correct
6 Correct 132 ms 12936 KB Output is correct
7 Correct 82 ms 12884 KB Output is correct
8 Correct 112 ms 12880 KB Output is correct
9 Correct 109 ms 12844 KB Output is correct
10 Correct 109 ms 12928 KB Output is correct
11 Correct 127 ms 12844 KB Output is correct
12 Correct 110 ms 12892 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -