oj.uz

Submission #811452

# Submission time Handle Problem Language Result Execution time Memory
811452 2023-08-07T04:26:29 Z vjudge1 Financial Report (JOI21_financial) C++14
5 / 100
 536 ms 32132 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]) ;
    }
    if(n <= 7000)
    {
        int ans = 0 ;
        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 << ans << '\n' ;
        return 0 ;
    }
    if(d == n)
    {
        int ans = 0 ;
        for(int i : s)
        {
            cnt++ ;
            mp[i] = cnt ;
        }
        for(int i = 1 ; i <= n ; i++)
        {
            a[i] = mp[a[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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 328 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 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Incorrect 0 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 328 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 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Incorrect 0 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 328 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 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Incorrect 0 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 1436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 1424 KB Output is correct
2 Correct 97 ms 1548 KB Output is correct
3 Correct 145 ms 1908 KB Output is correct
4 Correct 478 ms 32132 KB Output is correct
5 Correct 409 ms 32044 KB Output is correct
6 Correct 536 ms 32048 KB Output is correct
7 Correct 235 ms 32012 KB Output is correct
8 Correct 237 ms 31992 KB Output is correct
9 Correct 228 ms 31716 KB Output is correct
10 Correct 292 ms 31824 KB Output is correct
11 Correct 490 ms 32032 KB Output is correct
12 Correct 460 ms 32048 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 328 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 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Incorrect 0 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -