oj.uz

Submission #811513

# Submission time Handle Problem Language Result Execution time Memory
811513 2023-08-07T04:44:08 Z vjudge1 Financial Report (JOI21_financial) C++14
17 / 100
 1271 ms 36252 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = (1 << 19) ;
int n, d, cnt, a[N + 1], dp[N + 1], mx[2 * N + 1] ;
set<int> s ;
map<int, int> mp ;
void update(int l, int r, int ind, int num, int v)
{
    if(l > ind || r < ind)
        return ;
    if(l == r)
    {
        mx[v] = num ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    update(l, mid, ind, num, v * 2) ;
    update(mid + 1, r, ind, num, v * 2 + 1) ;
    mx[v] = max(mx[v * 2], mx[v * 2 + 1]) ;
}
int get_max(int l, int r,int l1, int r1, int v)
{
    if(l > r1 || r < l1)
        return 0 ;
    if(l1 <= l && r <= r1)
        return mx[v] ;
    int mid = (l + r) >> 1 ;
    return max(get_max(l, mid, l1, r1, v * 2), get_max(mid + 1, r, l1, r1, v * 2 + 1)) ;
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n >> d ;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i] ;
        s.insert(a[i]) ;
    }
    for(int i : s)
    {
        cnt++ ;
        mp[i] = cnt ;
    }
    for(int i = 1 ; i <= n ; i++)
        a[i] = mp[a[i]] ;
    if(d == 1)
    {
        int ans = 0 ;
        for(int i = 1 ; i <= n ; i++)
            update(1, N, i, a[i], 1) ;
        for(int i = n ; i >= 1 ; i--)
        {
            int l = i, r = n + 1 ;
            while(l + 1 < r)
            {
                int mid = (l + r) >> 1 ;
                if(get_max(1, N, i, mid, 1) > a[i])
                    r = mid ;
                else
                    l = mid ;
            }
            dp[i] = dp[r] + 1 ;
            ans = max(ans, dp[i]) ;
        }
        cout << ans ;
        return 0 ;
    }
    if(d == n)
    {
        int ans = 0 ;
        for(int i = 1 ; i <= n ; i++)
        {
            int num = get_max(1, N, 1, a[i] - 1, 1) ;
            ans = max(ans, num + 1) ;
            update(1, N, a[i], num + 1, 1) ;
        }
        cout << ans ;
        return 0 ;
    }
//    if(n <= 7000)
//    {
//        int ans = 0 ;
//        a[0] = -1 ;
//        for(int i = 1 ; i <= n ; i++)
//        {
//            int mx = 0 ;
//            for(int j = max(0, i - d) ; j < i ; j++)
//                if(a[j] < a[i])
//                    mx = max(mx, dp[j]) ;
//            dp[i] = mx + 1 ;
//            ans = max(ans, dp[i]) ;
//            cout << dp[i] << ' ' ;
//        }
//        cout << ans << '\n' ;
//        return 0 ;
//    }
    return 0 ;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Incorrect 0 ms 212 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Incorrect 0 ms 212 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Incorrect 0 ms 212 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1129 ms 5024 KB Output is correct
2 Correct 1006 ms 7704 KB Output is correct
3 Correct 993 ms 7964 KB Output is correct
4 Correct 1206 ms 32116 KB Output is correct
5 Correct 1156 ms 36020 KB Output is correct
6 Correct 1271 ms 36064 KB Output is correct
7 Correct 1170 ms 35888 KB Output is correct
8 Correct 1229 ms 36024 KB Output is correct
9 Correct 1091 ms 36252 KB Output is correct
10 Correct 1196 ms 36100 KB Output is correct
11 Correct 1139 ms 36112 KB Output is correct
12 Correct 1166 ms 36160 KB Output is correct
13 Correct 1138 ms 36036 KB Output is correct
14 Correct 1235 ms 36088 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 1536 KB Output is correct
2 Correct 98 ms 1536 KB Output is correct
3 Correct 139 ms 1904 KB Output is correct
4 Correct 387 ms 32076 KB Output is correct
5 Correct 314 ms 31948 KB Output is correct
6 Correct 392 ms 32044 KB Output is correct
7 Correct 216 ms 31948 KB Output is correct
8 Correct 224 ms 31952 KB Output is correct
9 Correct 225 ms 31772 KB Output is correct
10 Correct 282 ms 31872 KB Output is correct
11 Correct 369 ms 31968 KB Output is correct
12 Correct 344 ms 31972 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Incorrect 0 ms 212 KB Output isn't correct
12 Halted 0 ms 0 KB -