oj.uz

답안 #423476

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
423476 2021-06-11T07:54:12 Z 장태환(#7573) Financial Report (JOI21_financial) C++17
0 / 100
 5 ms 5196 KB 
#include <bits/stdc++.h>
using namespace std;
struct stree
{
    int st[600];
    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;
            continue;
        }
        int s=i+1;
        int e=su.size();
        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;
        ans=max(ans,va);
        dp.upd(x[i].second,ans);
    }
    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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 5196 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 5184 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -