Submission #696843

#	Time	Username	Problem	Language	Result	Execution time	Memory
696843		Do_you_copy	Financial Report (JOI21_financial)	C++17	100 / 100	464 ms	21728 KiB

Main

//Then
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(0); cin.tie(0);

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 4e5 + 1;
//const int Mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
int n, d;
int idx[maxN], dp[maxN];
int lab[maxN], minn[maxN];
int a[maxN];
int find_set(int u){
    return lab[u] < 0 ? u : lab[u] = find_set(lab[u]);
}

void unite(int u, int v){
    u = find_set(u);
    v = find_set(v);
    if (u == v) return;
    if (lab[u] > lab[v]) swap(u, v);
    minn[u] = min(minn[u], minn[v]);
    lab[u] += lab[v];
    lab[v] = u;
}

void join(int l, int r){
    if (abs(r - l) > d) return;
    unite(l, r);
}

struct TST{
    int st[maxN * 4];
    TST(){
        memset(st, 0, sizeof(st));
    }
    void update(int id, int i, int x, int l, int r){
        if (l == r){
            st[id] = x;
            return;
        }
        int mid = (l + r) >> 1;
        if (i <= mid) update(id << 1, i, x, l, mid);
        else update(id << 1 | 1, i, x, mid + 1, r);
        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }
    int get(int id, int i, int j, int l, int r){
        if (i > r || l > j) return 0;
        if (i <= l && r <= j) return st[id];
        int mid = (l + r) >> 1;
        return max(get(id << 1, i, j, l, mid), get(id << 1 | 1, i, j, mid + 1, r));
    }
};
TST st[2];

void Init(){
    cin >> n >> d;
    iota(minn, minn + n + 1, 1 - d);
    for (int i = 1; i <= n; ++i){
        minn[i] = max(0, minn[i]);
        cin >> a[i];
    }
    minn[0] = max(minn[0], 0);
    fill(lab, lab + n + 1, -1);
    iota(idx + 1, idx + n + 1, 1);
    sort(idx + 1, idx + n + 1,[&](const int &i, const int &j){
        if (a[i] == a[j]) return i < j;
        return a[i] < a[j];
    });
    int i = 1, j = 1;
    while (i <= n){
        while (j <= n && a[idx[j]] == a[idx[i]]){
            int pos = st[1].get(1, 0, idx[j], 0, n);
            int k;
            if (idx[j] - pos <= d)
                k = minn[find_set(pos)];
            else k = max(0, idx[j] - d);
            dp[idx[j]] = st[0].get(1, k, idx[j], 0, n) + 1;
            ++j;
        }
        while (i < j){
            int pos1 = st[1].get(1, 0, idx[i], 0, n);
            int pos2 = st[1].get(1, 0, idx[i] + d, 0, n);
            join(pos1, idx[i]);
            join(pos2, idx[i]);
            st[1].update(1, idx[i], idx[i], 0, n);
            st[0].update(1, idx[i], dp[idx[i]], 0, n);
            ++i;
        }
    }
    cout << *max_element(dp + 1, dp + n + 1);
}

#define debug
#define taskname "test"
signed main(){
    faster
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    int tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000);
        timeout.close();
        #ifndef debug
        cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n";
        #endif // debug
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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