Submission #593992

#	Time	Username	Problem	Language	Result	Execution time	Memory
593992		SOCIOPATE	Financial Report (JOI21_financial)	C++17	5 / 100	494 ms	29176 KiB

Main

#include <bits/stdc++.h>
#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <cmath>
#include <assert.h>
#include <ctime>
#include <math.h>
#include <queue>
#include <string>
#include <numeric>
#include <fstream>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <stack>
#include <random>
#include <list>
#include <bitset>
#include <algorithm>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

#define pll pair<ll, ll>
#define pii pair<int, int>
#define pdd pair<ld, ld>
#define ff first
#define ss second
#define all(v) v.begin(),v.end()

typedef tree<
    int,
    null_type,
    less<int>,
    rb_tree_tag,
    tree_order_statistics_node_update> ordset;


#pragma GCC optimize("-O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-Os")

ll INF = 2e18;

//mt19937 gen(time(0));

ll gcd(ll n, ll m){
    while(n != 0 && m != 0){
        if(n > m) n %= m;
        else m %= n;
    }
    return n + m;
}

ll lcm(ll n, ll m){
    ll nod = gcd(n, m);
    return n / nod * m;
}

ll mod = 1e9 + 7;

ll binpow(ll n, ll m){
    if(m == 0) return 1;
    if(m % 2ll == 1) {
        return (binpow(n, m - 1ll) * 1ll * n) % mod;
    }
    ll b = binpow(n, m / 2);
    return (b * 1ll * b) % mod;

}

vector<int> t;

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

int ask(int v, int l, int r, int askl, int askr){
    if(l >= askl && r <= askr) return t[v];
    if(l >= askr || r <= askl) return 0;
    int m = (l + r) / 2;
    return max(ask(2*v,l,m,askl,askr), ask(2*v+1,m,r,askl,askr));
}

void solve(){
    int n, d;
    cin >> n >> d;
    vector<int> a(n);
    vector<pii> b(n);
    t.resize(4*n, 0);
    for(int i = 0; i < n; i++){
        cin >> a[i];
        b[i] = {a[i], i};
    }
    sort(all(b));
    int cur = 0;
    for(int i = 0; i < n; i++){
        if(!i){
            a[b[i].ss] = cur;
            continue;
        }
        if(b[i].ff != b[i - 1].ff) cur++;
        a[b[i].ss] = cur;
    }
    vector<vector<int>> nums(n + 1);
    for(int i = 0; i < n; i++){
        nums[a[i]].push_back(i);
    }
    vector<int> res(n);
    for(int i = 0; i <= n; i++){
        for(int u : nums[i]){
            res[u] = 1;
            if(!u) continue;
            res[u] = ask(1, 0, n, max(u - d, 0), u) + 1;
        }
        for(int u : nums[i]){
            upd(1, 0, n, u, res[u]);
        }
        for(int u : nums[i]){
            if(!u) continue;
            res[u] = max(ask(1, 0, n, max(u - d, 0), u), res[u]);
        }
        for(int u : nums[i]){
            upd(1, 0, n, u, res[u]);
        }
    }
    cout << max(res[n - 1], ask(1, 0, n, max(n - 1 - d, 0), n - 1));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	int tt;
    //cin >> tt;
	tt = 1;
	while (tt--) {
		solve();
	}
	return 0;
}

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