oj.uz

Submission #811620

# Submission time Handle Problem Language Result Execution time Memory
811620 2023-08-07T05:08:12 Z vjudge1 Financial Report (JOI21_financial) C++14
31 / 100
 1559 ms 33348 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(n <= 7000)
    {
        int ans = 0 ;
        for(int i = n ; i >= 1 ; i--)
        {
            int mx = 0, now = a[i], mn = 1e9 ;
            for(int j = i + 1 ; j <= n ; j++)
            {
                mn = min(mn, a[j]) ;
                if(a[j] > now)
                    mx = max(mx, dp[j]) ;
                if((j - i) % d == 0)
                {
                    now = max(now, mn) ;
                    mn = 1e9 ;
                }
            }
            dp[i] = mx + 1 ;
            ans = max(ans, dp[i]) ;
        }
//        for(int i = 1 ; i <= n ; i++)
//            cout << dp[i] << ' ' ;
        cout << ans ;
        return 0 ;
    }
    if(n <= 20)
    {
        int ans = 0 ;
        for(int i = 0 ; i < (1 << n) ; i++)
        {
            int now = 0, mx = -1, ls = 1e9 ;
            for(int j = 0 ; j < n ; j++)
                if(j - ls <= d && ((1 << j) & i))
                {
                    ls = j ;
                    if(mx < a[j + 1])
                        now++ ;
                    mx = max(mx, a[j + 1]) ;
                }
            ans = max(ans, now) ;
        }
        cout << ans ;
        return 0 ;
    }
    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 ;
    }
    return 0 ;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 320 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 328 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 328 KB Output is correct
22 Correct 0 ms 332 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 1 ms 324 KB Output is correct
26 Correct 0 ms 340 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 320 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 328 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 328 KB Output is correct
22 Correct 0 ms 332 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 1 ms 324 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Incorrect 1 ms 340 KB Output isn't correct
29 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 320 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 328 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 328 KB Output is correct
22 Correct 0 ms 332 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 1 ms 324 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Incorrect 1 ms 340 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1195 ms 5080 KB Output is correct
2 Correct 1063 ms 5148 KB Output is correct
3 Correct 1031 ms 5068 KB Output is correct
4 Correct 1425 ms 29128 KB Output is correct
5 Correct 1331 ms 33288 KB Output is correct
6 Correct 1475 ms 33332 KB Output is correct
7 Correct 1145 ms 33064 KB Output is correct
8 Correct 1384 ms 33180 KB Output is correct
9 Correct 1124 ms 33248 KB Output is correct
10 Correct 1276 ms 33316 KB Output is correct
11 Correct 1204 ms 33296 KB Output is correct
12 Correct 1267 ms 33348 KB Output is correct
13 Correct 1305 ms 33276 KB Output is correct
14 Correct 1559 ms 33344 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 1736 KB Output is correct
2 Correct 122 ms 1796 KB Output is correct
3 Correct 200 ms 2192 KB Output is correct
4 Correct 759 ms 32308 KB Output is correct
5 Correct 561 ms 32296 KB Output is correct
6 Correct 734 ms 32296 KB Output is correct
7 Correct 230 ms 32204 KB Output is correct
8 Correct 313 ms 32300 KB Output is correct
9 Correct 265 ms 32076 KB Output is correct
10 Correct 343 ms 32144 KB Output is correct
11 Correct 586 ms 32296 KB Output is correct
12 Correct 398 ms 32304 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 320 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 328 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1 ms 328 KB Output is correct
22 Correct 0 ms 332 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 1 ms 324 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Incorrect 1 ms 340 KB Output isn't correct
29 Halted 0 ms 0 KB -