Submission #428677

#	Time	Username	Problem	Language	Result	Execution time	Memory
428677		muhammad_hokimiyon	Financial Report (JOI21_financial)	C++14	60 / 100	4045 ms	26172 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 = 3e5 + 7;
const long long mod = 1e9 + 7;

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

int p[N];
int t[4 * 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;
}

int get(int x, int l, int r, int tl, int tr)
{
        if(tl > tr)return 0;
        if(l == tl && r == tr){
                return t[x];
        }
        int m = (l + r) / 2;
        return max(get(x + x, l, m, tl, min(tr, m)),
                   get(x + x + 1, m + 1, r, max(tl, m + 1), tr));
}

void upd(int x, int l, int r, int pos, int val)
{
        if(l == r){
                t[x] = val;
                return;
        }
        int m = (l + r) / 2;
        if(pos <= m)upd(x + x, l, m, pos, val);
        else upd(x + x + 1, m + 1, r, pos, val);
        t[x] = max(t[x + x], t[x + x + 1]);
}

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);
        set<int> s;
        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;
                        auto gg = s.lower_bound(x);
                        if(!s.empty() && gg != s.begin()){
                                gg--;
                                if(x - *gg <= D)id = get(*gg);
                        }
                        if(id == -1){
                                g.push_back(1);
                                j++;
                                continue;
                        }
                        int l = 1, r = id;
                        while(l < r){
                                int m = (l + r) / 2;
                                gg = s.lower_bound(m);
                                if(get(*gg) == id)r = m;
                                else l = m + 1;
                        }
                        mx = get(1, 1, n, l, x) + 1;
                        g.push_back(mx);
                        j++;
                }
                for(int h = i; h < j; h++){
                        d[id[h]] = g[h - i];
                        s.insert(id[h]);
                        upd(1, 1, n, id[h], d[id[h]]);
                }
                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: 12 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35