Submission #763117

#	Time	Username	Problem	Language	Result	Execution time	Memory
763117		vjudge1	Financial Report (JOI21_financial)	C++17	100 / 100	846 ms	66888 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn = 3e5;

struct gay
{
    ll value;
    ll index;
};
ll par[maxn], top[maxn];
ll find(ll a) {return par[a] = par[a]==a ? a : find(par[a]);}

bool same(ll a, ll b) {return find(a) == find(b);}

void init(ll n)
{
    for (ll i = 1; i <= n; ++i)
    {
        par[i] = i;
        top[i] = i;
    }
}
void united(ll a, ll b) 
{
    a = find(a);
    b = find(b);
    if (a == b) return;

    par[b] = a;
    top[a] = min(top[a], top[b]);
}
bool cmp(const gay &a, const gay &b) 
{
    if (a.value != b.value) return a.value < b.value;
    return a.index > b.index;

}
ll tree[4 * maxn];

void update(ll id, ll l, ll r, ll pos, ll val)
{
    if (l == r)
    {
        tree[id] = val;
        return;
    }
    
    ll mid = (l + r) >> 1;
    if (pos <= mid) update(id << 1, l, mid, pos, val);
    else update((id << 1) + 1, mid + 1, r, pos, val);

    tree[id] = max(tree[id * 2], tree[id * 2 + 1]);
}

ll get(ll id, ll l, ll r, ll ql, ll qr)
{
    if (l > qr || r < ql) return 0;
    if (l >= ql && r <= qr) return tree[id];

    ll mid = (l + r) >> 1;

    if (qr <= mid) return get(id << 1, l, mid, ql, qr);
    else if (ql >= mid + 1) return get((id << 1) + 1, mid + 1, r, ql, qr);
    else return max(get(id << 1, l, mid, ql, qr), get((id << 1) + 1, mid + 1, r, ql, qr));
}

int main()
{
    ll n, d;
    cin >> n >> d;
    init(n);
    gay a[n + 1];
    a[0].value = 0;
    set<ll> mark;
    map<ll, ll> bullshit;
    for (ll i = 1; i <= n; ++i) 
    {
        cin >> a[i].value;
        mark.insert(a[i].value);
        a[i].index = i;
    }
    ll mark2 = 0;
    for (auto cum: mark) bullshit[cum] = ++mark2;

    for (ll i = 1; i <= n; ++i) 
    {
        a[i].value = bullshit[a[i].value];
        //update(1, 1, n, i, a[i].value);
        //cout << a[i].value << " ";
    }
    //cout << endl;
    sort(a + 1, a + n + 1, cmp);
    //for (ll i = 1; i <= n; ++i) cout << a[i].value << " " <<  a[i].index << ") ";
    //cout << endl;
    set<ll> sex;
    ll maxt = -1;
    for (ll i = 1; i <= n; ++i)
    {
        auto omg = sex.lower_bound(a[i].index);
        if (omg != sex.end()) 
        {
            if (d - abs(*omg - a[i].index) >= 0) united(*omg, a[i].index);
        }
        
        if (omg != sex.begin()) 
        {
            omg--;
            if (d - abs(*omg - a[i].index) >= 0) united(*omg, a[i].index);
        }
        sex.insert(a[i].index);
        ll dp = 1;
        ll shit = find(a[i].index);
        if (top[shit] <= a[i].index - 1) dp = max(dp, 1 + get(1, 1, n, top[shit], a[i].index - 1));
        update(1, 1, n, a[i].index, dp);
        //maxt = max(maxt, dp);
    }
    cout << get(1, 1, n, 1, n);
    
    
    //for (ll i = 1; i <= n; ++i) cout << a[i].index << " ";

    


}
// ll dp[maxn];
// int main()
// {
//     ll n, d;
//     cin >> n >> d;
//     ll a[n + 1];
//     ll maxt = -1;
//     for (ll i = 1; i <= n; ++i) cin >> a[i];
//     dp[1] = 1;
//     for (ll i = 2; i <= n; ++i) 
//     {
//         for (ll j = i - 1; j >= i - d; --j)
//         {
//             if (j <= 0) break;
//             if (a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);
//         }
//         maxt = max(maxt, dp[i]);
//     }
//     cout << maxt;
// }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:97:8: warning: unused variable 'maxt' [-Wunused-variable]
   97 |     ll maxt = -1;
      |        ^~~~

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