Submission #594000

#	Time	Username	Problem	Language	Result	Execution time	Memory
594000		SOCIOPATE	Financial Report (JOI21_financial)	C++17	100 / 100	1118 ms	43228 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;

}

int n, d;

struct str{
    int l, r, ans;
};

vector<int> t;
vector<str> t2;

str comb(str a, str b){
    if(a.l == -1) return b;
    if(b.l == -1) return a;
    str res;
    res.l = a.l;
    res.r = b.r;
    res.ans= max(a.ans, b.ans);
    if(b.l - a.r > d) res.ans = max(res.ans, b.l);
    return res;
}

void upd(int v, int l, int r, int pos, int val){
    if(l == r - 1){
        t[v] = val;
        t2[v] = {l, l, -1};
        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]);
    t2[v] = comb(t2[2*v],t2[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));
}

str ask2(int v, int l, int r, int askl, int askr){
    if(l >= askl && r <= askr) return t2[v];
    if(l >= askr || r <= askl) return {-1, -1, -1};
    int m = (l + r) / 2;
    return comb(ask2(2*v,l,m,askl,askr), ask2(2*v+1,m,r,askl,askr));
}

void solve(){
    cin >> n >> d;
    vector<int> a(n);
    vector<pii> b(n);
    t.resize(4*n, 0);
    t2.resize(4*n, {-1, -1, -1});
    for(int i = 0; i < n; i++){
        cin >> a[i];
        b[i] = {a[i], i};
    }
    if(n == 1){
        cout << 1;
        return;
    }
    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;
            str y = ask2(1, 0, n, 0, u + 1);
            //cout << u << " " << y.r << '\n';
            if(u - y.r > d) continue;
            res[u] = ask(1, 0, n, (y.ans == -1 ? 0 : y.ans), u + 1) + 1;
        }
        for(int u : nums[i]){
            upd(1, 0, n, u, res[u]);
        }
        for(int u : nums[i]){
            if(!u) continue;
            str y = ask2(1, 0, n, 0, u + 1);
            if(u - y.r > d) continue;
            res[u] = max(ask(1, 0, n, (y.ans == -1 ? 0 : y.ans), u + 1), res[u]);
        }
        for(int u : nums[i]){
            //cout << u << " " << res[u] << '\n';
            upd(1, 0, n, u, res[u]);
        }
    }
    int ans = 1;
    for(int u : res) ans = max(u, ans);
    cout << ans;
}

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

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