oj.uz

Submission #813402

# Submission time Handle Problem Language Result Execution time Memory
813402 2023-08-07T17:05:44 Z ZHIRDILBILDIZ Financial Report (JOI21_financial) C++14
0 / 100
 2173 ms 8532 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, ans, dp[N + 1], p[N + 1], kol[N + 1], mn[N + 1], mx[N + 1] ;
pair<int, int> a[N + 1] ;
int get(int a)
{
    while(a != p[a])
        a = p[a] ;
    return a ;
}
void join(int a, int b)
{
    a = get(a) ;
    b = get(b) ;
    if(a == b)
        return ;
    if(kol[a] > kol[b])
        swap(a, b) ;
    mn[b] = min(mn[a], mn[b]) ;
    kol[b] += kol[a] ;
    kol[a] = 0 ;
    p[a] = b ;
}
int get_min(int a)
{
    a = get(a) ;
    return mn[a] ;
}
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)) ;
}
bool cmp(pair<int, int> p1, pair<int, int> p2)
{
    if(p1.fi != p2.fi)
        return p1.fi < p2.fi ;
    else
        return p1.se > p2.se ;
}
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].fi ;
        p[i] = i ;
        mn[i] = i ;
        kol[i] = 1 ;
        a[i].se = i ;
    }
    sort(a + 1, a + n + 1, cmp) ;
    for(int i = 1 ; i <= n ; i++)
    {
        cnt++ ;
        a[i].fi = cnt ;
    }
//    for(int i = 1 ; i <= n ; i++)
//        cout << a[i].fi << ' ' << a[i].se << '\n' ;
//    cout << "_______________________\n" ;
    for(int i = 1 ; i <= n ; i++)
    {
        int l = max(1, a[i].se - d), r = a[i].se + 1 ;
        while(l + 1 < r)
        {
            int mid = (l + r) >> 1 ;
            if(get_max(1, N, mid, a[i].se, 1))
                l = mid ;
            else
                r = mid ;
        }
        join(l, a[i].se) ;
//        cout << l << ' ' ;
        l = get_min(l) ;
        int num = get_max(1, N, l, a[i].se, 1) + 1 ;
        dp[a[i].se] = num ;
//        cout << l << ' ' << a[i].se << ' ' << num << ' ' ;
        update(1, N, a[i].se, num, 1) ;
        l = a[i].se, r = min(n, a[i].se + d) ;
        while(l + 1 < r)
        {
            int mid = (l + r) >> 1 ;
            if(get_max(1, N, a[i].se + 1, mid, 1))
                r = mid ;
            else
                l = mid ;
        }
//        cout << r << '\n' ;
        if(r >= a[i].se + 1 && get_max(1, N, a[i].se + 1, r, 1))
            join(r, a[i].se) ;
        ans = max(ans, dp[a[i].se]) ;
    }
    cout << ans ;
    return 0 ;
}
//7 2
//8 1 7 3 2 6 5

Subtask #1
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 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 1 ms 384 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 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 1 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 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 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 1 ms 384 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 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 1 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 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 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 1 ms 384 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 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 1 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 207 ms 8532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

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

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 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 1 ms 384 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 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 1 ms 340 KB Output is correct
15 Incorrect 0 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -