oj.uz

Submission #423489

# Submission time Handle Problem Language Result Execution time Memory
423489 2021-06-11T07:59:42 Z 장태환(#7573) Financial Report (JOI21_financial) C++17
0 / 100
 534 ms 16460 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 ans=-(1<<30);
        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));
    }
    cma.init(su);
    for(i=0;i<N;i++)
    {
        if(i>=su.size()+2)
        {
            lim[i]=N-1;
            continue;
        }
        int s=i+1;
        int e=su.size()-1;
        while(s<e)
        {
            int m=(s+e)>>1;
            if(cma.q(i+1,m+1)<=arr[i])
                s=m+1;
            else
                e=m;
        }
        lim[i]=e+M;
    }
    int ans=0;
    for(i=0;i<N;i++)
    {
        int va=dp.q(x[i].second+1,lim[x[i].second]+1)+1;
        ans=max(ans,va);
        dp.upd(x[i].second,va);
    }
    cout << ans;
}

Compilation message

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

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 16460 KB Output is correct
2 Correct 443 ms 16428 KB Output is correct
3 Incorrect 417 ms 16444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 12840 KB Output is correct
2 Correct 120 ms 12844 KB Output is correct
3 Correct 130 ms 12872 KB Output is correct
4 Correct 152 ms 12892 KB Output is correct
5 Correct 133 ms 12884 KB Output is correct
6 Correct 138 ms 12924 KB Output is correct
7 Incorrect 90 ms 12864 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -