Submission #1025033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025033		KienTran	Financial Report (JOI21_financial)	C++14	100 / 100	387 ms	73848 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int O = 3e5 + 5;
const int P = (1 << 10) + 5;
const int mod = 998244353;
const int inf = 1e9;
int pr[] = {167772161, 469762049, 754974721, 1045430273, 1051721729, 1053818881};

int n, D, res, a[O], rp[O], f[21][O];
vector <pair <int, int>> val;
int tree[O * 4];

void Update(int id, int l, int r, int u, int val){
    if (l > u || r < u) return;
    if (l == r){
        tree[id] = val;
        return;
    }
    int mid = (l + r) / 2;
    Update(id << 1, l, mid, u, val);
    Update(id << 1 | 1, mid + 1, r, u, val);
    tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
}

int Get(int id, int l, int r, int u, int v){
    if (l > v || r < u) return 0;
    if (u <= l && r <= v) return tree[id];
    int mid = (l + r) / 2;
    return max(Get(id << 1, l, mid, u, v), Get(id << 1 | 1, mid + 1, r, u, v));
}

int Get(int l, int r){
    int len = log2(r - l + 1);
    return min(f[len][l], f[len][r - (1 << len) + 1]);
}

main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> D;
    for (int i = 1; i <= n; ++ i){
        cin >> a[i];
        f[0][i] = a[i];
        val.push_back({a[i], i});
    }

    for (int i = 1; i <= 20; ++ i){
        for (int j = 1; j - 1 + (1 << i) <= n; ++ j){
            f[i][j] = min(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
        }
    }

    sort(val.begin(), val.end());
    for (int i = 1; i <= n; ++ i){
        rp[val[i - 1].second] = i;
    }

    priority_queue <pair <int, int>> q;
    for (int i = 1; i <= n; ++ i){
        int id = upper_bound(val.begin(), val.end(), make_pair(a[i] - 1, n)) - val.begin();
        int dp = Get(1, 1, n, 1, id) + 1;
        res = max(res, dp);

        //cout << i << " " << dp << " " << id << endl;

        Update(1, 1, n, rp[i], dp);
        if (i > D){
            int x = Get(i - D + 1, i);

            while (q.size() && -q.top().first < x){
                auto z = q.top(); q.pop();
                Update(1, 1, n, rp[z.second], 0);
            }
        }

        if (i >= D) q.push({-a[i - D + 1], i - D + 1});
    }

    cout << res;
}
/**
1
8
34124838 0 113193378 8 321939321 113193378 9463828 99
**/

Compilation message (stderr)

Main.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main(){
      | ^~~~

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