Submission #556036

#	Time	Username	Problem	Language	Result	Execution time	Memory
556036		MrKustic	Financial Report (JOI21_financial)	C++17	5 / 100	846 ms	46204 KiB

Main

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb emplace_back
#define x first
#define y second

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pt;
typedef pair<ll, ll> ptll;
//typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//typedef gp_hash_table<int, int> table;

void fastio(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,sse3,ssse3,sse4.1,sse4.2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("inline")
*/

//-------------------------------------------

const int MAXN = 3e5 + 10;

int a[MAXN];

void coordinate_compression(int n, int t){
    vector<pt> coords(n);
    for (int i = 0; i < n; i++)
        coords[i] = {a[i], i};
    sort(all(coords));
    a[coords[0].y] = 1;
    for (int i = 1; i < n; i++){
        if (coords[i].x != coords[i - 1].x)
            t++;
        a[coords[i].y] = t;
    }
}

int jmp[MAXN];
int p[MAXN];
int r[MAXN];
int val[MAXN];

vector<int> arev[MAXN];

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

void Union(int x, int y){
    x = get(x), y = get(y);
    if (r[x] > r[y])
        swap(x, y);
    p[x] = y;
    if (r[x] == r[y])
        r[y]++;
    val[y] = max(val[y], val[x]);
}

void longest_jump(int n, int d){
    iota(p, p + n, 0);
    iota(val, val + n, 0);
    fill(r, r + n, 1);
    for (int i = 0; i < n; i++){
        arev[a[i]].push_back(i);
    }
    set<int> used;
    for (int x = 1; x <= n + 1; x++){
        for (int i: arev[x]){
            used.insert(i);
            auto it = used.find(i);
            if (it != used.begin()){
                int j = *(--it);
                if (i - j <= d)
                    Union(i, j);
                it++;
            }
            it++;
            if (it != used.end()){
                int j = *it;
                if (j - i <= d)
                    Union(i, j);
            }
        }
        for (int i: arev[x]){
            jmp[i] = min(n - 1, val[get(i)] + d) + 1;
        }
    }
}

int tree[MAXN << 2];

void upd(int v, int lt, int rt, int pos, int nw){
    if (rt - lt == 1){
        tree[v] = nw;
        return;
    }
    int m = (lt + rt) >> 1;
    if (pos < m)
        upd(v << 1, lt, m, pos, nw);
    else
        upd(v << 1 | 1, m, rt, pos, nw);
    tree[v] = max(tree[v << 1], tree[v << 1 | 1]);
}

int getmax(int v, int lt, int rt, int ql, int qr){
    if (rt <= ql || qr <= lt)
        return 0;
    if (ql <= lt && rt <= qr)
        return tree[v];
    int m = (lt + rt) >> 1;
    return max(getmax(v << 1, lt, m, ql, qr), getmax(v << 1 | 1, m, rt, ql, qr));
}

int dp[MAXN];
int rt[MAXN];

void calc_dp(int n){
    fill(dp, dp + n, 1);
    fill(rt, rt + MAXN + 1, -1);
    set<pt> st;
    for (int i = 0; i < n; i++){
        while (!st.empty() && (*st.begin()).x == i){
            int prv = (*st.begin()).y;
            upd(1, 1, MAXN + 1, prv, 0);
            rt[prv] = -1;
            st.erase(st.begin());
        }
        int mx = getmax(1, 1, MAXN + 1, 1, a[i]) + 1;
        dp[i] = mx;
        if (rt[a[i]] != -1){
            st.erase({rt[a[i]], a[i]});
        }
        rt[a[i]] = jmp[i];
        upd(1, 1, MAXN + 1, a[i], mx);
        st.insert({rt[a[i]], a[i]});
    }
}

void run(){
    int n, d;
    cin >> n >> d;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    coordinate_compression(n, 1);
    longest_jump(n, d);
    calc_dp(n);
    int ans = 1;
    for (int i = 0; i < n; i++){
        if (jmp[i] == n)
            ans = max(ans, dp[i]);
    }
    cout << ans;
}

int main(){
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#else
    fastio();
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
#endif
    auto start = chrono::high_resolution_clock::now();
    run();
    auto stop = chrono::high_resolution_clock::now();
#ifdef LOCAL
    cerr << "Program finished in " << (ld)chrono::duration_cast<chrono::milliseconds>(stop - start).count() / 1e3 << " sec";
#endif
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:178:10: warning: variable 'start' set but not used [-Wunused-but-set-variable]
  178 |     auto start = chrono::high_resolution_clock::now();
      |          ^~~~~
Main.cpp:180:10: warning: variable 'stop' set but not used [-Wunused-but-set-variable]
  180 |     auto stop = chrono::high_resolution_clock::now();
      |          ^~~~
Main.cpp: In function 'void calc_dp(int)':
Main.cpp:134:9: warning: array subscript 300011 is outside array bounds of 'int [300010]' [-Warray-bounds]
  134 |     fill(rt, rt + MAXN + 1, -1);
      |     ~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:130:5: note: while referencing 'rt'
  130 | int rt[MAXN];
      |     ^~

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