oj.uz

답안 #362938

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
362938 2021-02-04T18:55:46 Z shahriarkhan Global Warming (CEOI18_glo) C++14
48 / 100
 2000 ms 52692 KB 
#include<bits/stdc++.h>
using namespace std ;

int mx = 7e5 ;

map<int,int> mp ;

vector<int> V ;

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 , int val)
    {
        if(low>ind || high<ind) return ;
        if(low==high && low==ind)
        {
            t[node] = val ;
            return ;
        }
        int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
        update(left,low,mid,ind,val) , update(right,mid+1,high,ind,val) ;
        t[node] = max(t[left],t[right]) ;
    }

    void clean(int node , int low , int high)
    {
        if(low==high)
        {
            t[node] = 0 ;
            return ;
        }
        int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
        clean(left,low,mid) , clean(right,mid+1,high) ;
        t[node] = 0 ;
    }

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

int main()
{
    int n , x , ind = 0 ;
    scanf("%d%d",&n,&x) ;
    int a[n+1] , ans = 0 , dp[n+2][3] ;
    for(int i = 1 ; i <= n ; ++i)
    {
        scanf("%d",&a[i]) ;
        V.push_back(a[i]) ;
        V.push_back(a[i] + x - 1) ;
        V.push_back(a[i] - x + 1) ;
        dp[i][1] = 0 , dp[i][2] = 0 ;
    }
    sort(V.begin(),V.end()) ;
    for(int i : V)
    {
        if(mp[i]) continue ;
        mp[i] = ++ind ;
    }
    ++ind , ++ind ;
    mx = ind ;
    tree pref(mx+5) , suf(mx+5) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        dp[i][1] = pref.query(1,0,mx,1,mp[a[i] + x - 1]) ;
        pref.update(1,0,mx,mp[a[i]],pref.query(1,0,mx,1,mp[a[i]] - 1) + 1) ;
    }
    for(int i = n ; i >= 1 ; --i)
    {
        dp[i][2] = suf.query(1,0,mx,mp[a[i]-x+1],mx) ;
        suf.update(1,0,mx,mp[a[i]],suf.query(1,0,mx,mp[a[i]] + 1,mx) + 1) ;
    }
    pref.clean(1,0,mx) , suf.clean(1,0,mx) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        ans = max(ans,dp[i][2] + pref.query(1,0,mx,1,mp[a[i]] - 1) + 1) ;
        pref.update(1,0,mx,mp[a[i]],pref.query(1,0,mx,1,mp[a[i]] - 1) + 1) ;
    }
    for(int i = n ; i >= 1 ; --i)
    {
        ans = max(ans,dp[i][1] + suf.query(1,0,mx,mp[a[i]] + 1,mx) + 1) ;
        suf.update(1,0,mx,mp[a[i]],suf.query(1,0,mx,mp[a[i]] + 1,mx) + 1) ;
    }
    printf("%d\n",ans) ;
    return 0 ;
}

Compilation message

glo.cpp: In function 'int main()':
glo.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |     scanf("%d%d",&n,&x) ;
      |     ~~~~~^~~~~~~~~~~~~~
glo.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |         scanf("%d",&a[i]) ;
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 0 ms 364 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 0 ms 364 KB Output is correct
19 Correct 4 ms 620 KB Output is correct
20 Correct 4 ms 620 KB Output is correct
21 Correct 4 ms 620 KB Output is correct
22 Correct 4 ms 620 KB Output is correct
23 Correct 2 ms 492 KB Output is correct
24 Correct 3 ms 492 KB Output is correct
25 Correct 2 ms 492 KB Output is correct
26 Correct 3 ms 492 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2076 ms 52692 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 387 ms 13628 KB Output is correct
2 Correct 379 ms 13408 KB Output is correct
3 Correct 387 ms 13484 KB Output is correct
4 Correct 174 ms 7520 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 142 ms 3680 KB Output is correct
7 Correct 272 ms 10896 KB Output is correct

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 962 ms 26628 KB Output is correct
2 Correct 944 ms 26716 KB Output is correct
3 Execution timed out 2055 ms 52692 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 0 ms 364 KB Output is correct
19 Correct 4 ms 620 KB Output is correct
20 Correct 4 ms 620 KB Output is correct
21 Correct 4 ms 620 KB Output is correct
22 Correct 4 ms 620 KB Output is correct
23 Correct 2 ms 492 KB Output is correct
24 Correct 3 ms 492 KB Output is correct
25 Correct 2 ms 492 KB Output is correct
26 Correct 3 ms 492 KB Output is correct
27 Execution timed out 2076 ms 52692 KB Time limit exceeded
28 Halted 0 ms 0 KB -