제출 #362832

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
362832		shahriarkhan	Money (IZhO17_money)	C++14	0 / 100	16 ms	23788 KiB

money

#include<bits/stdc++.h>
using namespace std ;

const int mx = 1e6 + 5 ;

struct tree
{
    vector<int> t ;

    tree(int n)
    {
        t = vector<int> (4*n + 4 , 0) ;
    }

    void update(int node , int low , int high , int ind)
    {
        if(high<ind || low>ind) return ;

        if(low==high && high==ind)
        {
            t[node] = 1 ;
            return ;
        }

        int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
        update(left,low,mid,ind) ;
        update(right,mid+1,high,ind) ;
        t[node] = max(t[left],t[right]) ;
    }

    int find_max(int node , int low , int high , int l , int r)
    {
        if(l>r) return 0 ;
        if(l>high || r<low) return 0 ;
        if(l<=low && high<=r) return t[node] ;
        int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
        return max(find_max(left,low,mid,l,r),find_max(right,mid+1,high,l,r)) ;
    }
};

int main()
{
    int n ;
    scanf("%d",&n) ;
    int a[n+1] , b[n+1] , prev = 0 , ans = 0 ;
    vector<int> ind[mx] ;
    for(int i = 1 ; i <= n ; ++i) scanf("%d",&a[i]) , b[i] = a[i] ;
    sort(b+1,b+n+1) ;
    for(int i = n ; i >= 1 ; --i)
    {
        ind[b[i]].push_back(i) ;
    }
    for(int i = 1 ; i <= n ; ++i)
    {
        int old = a[i] ;
        a[i] = ind[a[i]].back() ;
        ind[old].pop_back() ;
    }
    tree T(n+5) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        if(!prev)
        {
            T.update(1,1,n,a[i]) , ++ans ;
            prev = a[i] ;
            continue ;
        }
        if(a[i]<prev) prev = a[i] , ++ans ;
        else if(T.find_max(1,1,n,prev+1,a[i])) prev = a[i] , ++ans ;
        else prev = a[i] ;
        T.update(1,1,n,a[i]) ;
    }
    printf("%d\n",ans) ;
    return 0 ;
}

컴파일 시 표준 에러 (stderr) 메시지

money.cpp: In function 'int main()':
money.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |     scanf("%d",&n) ;
      |     ~~~~~^~~~~~~~~
money.cpp:47:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |     for(int i = 1 ; i <= n ; ++i) scanf("%d",&a[i]) , b[i] = a[i] ;
      |                                   ~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55