Submission #428654

#	Time	Username	Problem	Language	Result	Execution time	Memory
428654		muhammad_hokimiyon	Financial Report (JOI21_financial)	C++14	48 / 100	4067 ms	5108 KiB

Main

#include <bits/stdc++.h>

#define fi first
#define se second
#define ll long long
#define dl double

using namespace std;

const int N = 1e6 + 7;
const long long mod = 1e9 + 7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int p[N];

int get(int x)
{
        return (p[x] == x ? x : p[x] = get(p[x]));
}

void meg(int x, int y)
{
        x = get(x);
        y = get(y);
        p[y] = x;
}

void solve()
{
        int n,D;
        cin >> n >> D;
        vector<int> a(n + 1, 0);
        vector<int> id;
        for(int i = 1; i <= n; i++){
                cin >> a[i];
                id.push_back(i);
                p[i] = i;
        }
        sort(id.begin(), id.end(), [&](int i, int j){
                return a[i] < a[j];
        });
        vector<int> d(n + 1, 0);
        for(int i = 0; i < n; i++){
                int j = i;
                vector<int> g;
                while(j < n && a[id[i]] == a[id[j]]){
                        int x = id[j];
                        int mx = 1;
                        int id = -1;
                        for(int h = x; h >= max(1, x - D); h--){
                                if(d[h] > 0){
                                        id = get(h);
                                        break;
                                }
                        }
                        for(int h = x; h >= 1; h--){
                                if(get(h) == id)mx = max(mx, d[h] + 1);
                        }
                        g.push_back(mx);
                        j++;
                }
                for(int h = i; h < j; h++){
                        d[id[h]] = g[h - i];
                }
                for(int h = i; h < j; h++){
                        int st = id[h];
                        for(int g = max(1, st - D); g <= min(n, st + D); g++){
                                if(d[g] > 0){
                                        meg(st, g);
                                }
                        }
                }
                i = j - 1;
        }
        cout << *max_element(d.begin(), d.end());
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen( "input.txt" , "r" , stdin );
    //freopen( "output.txt" , "w" , stdout );

    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 0 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35