oj.uz

답안 #423500

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
423500 2021-06-11T08:08:31 Z 장태환(#7573) Financial Report (JOI21_financial) C++17
5 / 100
 535 ms 16516 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++)
    {
        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,0)<=-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,0)+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

# 결과 실행 시간 메모리 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 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 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 0 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 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 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 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 0 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 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 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 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 0 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 535 ms 16516 KB Output is correct
2 Correct 466 ms 16392 KB Output is correct
3 Incorrect 445 ms 16460 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 12916 KB Output is correct
2 Correct 122 ms 12816 KB Output is correct
3 Correct 133 ms 12900 KB Output is correct
4 Correct 134 ms 12888 KB Output is correct
5 Correct 117 ms 12840 KB Output is correct
6 Correct 124 ms 12920 KB Output is correct
7 Correct 78 ms 12924 KB Output is correct
8 Correct 79 ms 13008 KB Output is correct
9 Correct 85 ms 12824 KB Output is correct
10 Correct 110 ms 12808 KB Output is correct
11 Correct 136 ms 12884 KB Output is correct
12 Correct 107 ms 12884 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 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 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 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 0 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -