Submission #813508

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
813508	2023-08-07T19:15:00 Z	ZHIRDILBILDIZ	Financial Report (JOI21_financial)	C++14	0 / 100	2371 ms	9760 KB

Main

#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[2 * N + 1], mx[2 * 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++)
    {
        int l1 = 0, r1 = a[i].se + 1, l2 = a[i].se - 1, r2 = n + 1, num = 1 ;
        dp[a[i].se] = 1 ;
        while(l1 + 1 < r1)
        {
            int mid = (l1 + r1) >> 1 ;
            if(get_max(1, N, mid, a[i].se, 1))
                l1 = mid ;
            else
                r1 = mid ;
        }
        while(l2 + 1 < r2)
        {
            int mid = (l2 + r2) >> 1 ;
            if(get_max(1, N, a[i].se, mid, 1))
                r2 = mid ;
            else
                l2 = mid ;
        }
        if(r2 - a[i].se <= d)
        {
            num = get_max(1, N, a[i].se, r2, 1) ;
            if(num)
                join(a[i].se, r2) ;
        }
        if(a[i].se - l1 <= d)
        {
            num = get_max(1, N, l1, a[i].se, 1) ;
            if(num)
                join(a[i].se, l1) ;
            dp[a[i].se] = num + 1 ;
            update(1, N, a[i].se, num + 1, 1) ;
        }
        else
            update(1, N, a[i].se, 1, 1) ;
//        cout<<l1<<' '<<r2<<' '<<a[i].se<<' '<<dp[a[i].se] << '\n' ;
        ans = max(ans, dp[a[i].se]) ;
    }
    cout << ans ;
    return 0 ;
}
//8 8
//4 5 1 3 6 2 7 10

Subtask #1
0 / 14.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Correct	340 KB	Output is correct
3	Correct	340 KB	Output is correct
4	Correct	340 KB	Output is correct
5	Correct	340 KB	Output is correct
6	Correct	340 KB	Output is correct
7	Correct	340 KB	Output is correct
8	Correct	340 KB	Output is correct
9	Correct	340 KB	Output is correct
10	Correct	340 KB	Output is correct
11	Correct	340 KB	Output is correct
12	Correct	340 KB	Output is correct
13	Correct	340 KB	Output is correct
14	Correct	340 KB	Output is correct
15	Incorrect	340 KB	Output isn't correct
16	Halted	0 KB	-

Subtask #2
0 / 14.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Correct	340 KB	Output is correct
3	Correct	340 KB	Output is correct
4	Correct	340 KB	Output is correct
5	Correct	340 KB	Output is correct
6	Correct	340 KB	Output is correct
7	Correct	340 KB	Output is correct
8	Correct	340 KB	Output is correct
9	Correct	340 KB	Output is correct
10	Correct	340 KB	Output is correct
11	Correct	340 KB	Output is correct
12	Correct	340 KB	Output is correct
13	Correct	340 KB	Output is correct
14	Correct	340 KB	Output is correct
15	Incorrect	340 KB	Output isn't correct
16	Halted	0 KB	-

Subtask #3
0 / 20.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Correct	340 KB	Output is correct
3	Correct	340 KB	Output is correct
4	Correct	340 KB	Output is correct
5	Correct	340 KB	Output is correct
6	Correct	340 KB	Output is correct
7	Correct	340 KB	Output is correct
8	Correct	340 KB	Output is correct
9	Correct	340 KB	Output is correct
10	Correct	340 KB	Output is correct
11	Correct	340 KB	Output is correct
12	Correct	340 KB	Output is correct
13	Correct	340 KB	Output is correct
14	Correct	340 KB	Output is correct
15	Incorrect	340 KB	Output isn't correct
16	Halted	0 KB	-

Subtask #4
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2037 ms	9740 KB	Output is correct
2	Incorrect	2139 ms	9760 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2095 ms	9676 KB	Output is correct
2	Incorrect	2371 ms	9760 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #6
0 / 35.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Correct	340 KB	Output is correct
3	Correct	340 KB	Output is correct
4	Correct	340 KB	Output is correct
5	Correct	340 KB	Output is correct
6	Correct	340 KB	Output is correct
7	Correct	340 KB	Output is correct
8	Correct	340 KB	Output is correct
9	Correct	340 KB	Output is correct
10	Correct	340 KB	Output is correct
11	Correct	340 KB	Output is correct
12	Correct	340 KB	Output is correct
13	Correct	340 KB	Output is correct
14	Correct	340 KB	Output is correct
15	Incorrect	340 KB	Output isn't correct
16	Halted	0 KB	-

Submission #813508

Compilation message

Subtask #1 0 / 14.0

Subtask #2 0 / 14.0

Subtask #3 0 / 20.0

Subtask #4 0 / 12.0

Subtask #5 0 / 5.0

Subtask #6 0 / 35.0

Subtask #1
0 / 14.0

Subtask #2
0 / 14.0

Subtask #3
0 / 20.0

Subtask #4
0 / 12.0

Subtask #5
0 / 5.0

Subtask #6
0 / 35.0