Submission #892579

#	Time	Username	Problem	Language	Result	Execution time	Memory
892579		quochuy147	Financial Report (JOI21_financial)	C++14	100 / 100	711 ms	49988 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define all(x) (x).begin() , (x).end()
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define file "name"
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}

const int inf = 1e9 + 5;
const ll linf = 1e17;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
const int LOG = 20;

int n, d, res;
int a[N], f[N], lim[N];
int rmq[N][LOG + 5], lg[N];
pii b[N];
set <int> s;
map <int, int> x;
vector <int> pos[N];

void inp()
{
    cin >> n >> d;
    for(int i = 1; i <= n; ++i) cin >> a[i];
}

namespace sub4 {
    void prepare() {
        for(int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;

        for(int i = 1; i <= n; ++i) rmq[i][0] = a[i];
        for(int j = 1; j <= LOG; ++j)
            for(int i = 1; i + MASK(j) - 1 <= n; ++i) rmq[i][j] = max(rmq[i][j - 1], rmq[i + MASK(j - 1)][j - 1]);
    }

    int get(int l, int r) {
        int k = lg[r - l + 1];
        return max(rmq[l][k], rmq[r - MASK(k) + 1][k]);
    }

    void solve() {
        prepare();
        for(int i = n; i >= 1; --i) {
            int l = i + 1, r = n, id = n + 1;
            while(l <= r) {
                int m = (l + r) >> 1;
                if(get(i, m) > a[i]) {
                    id = m;
                    r = m - 1;
                }
                else l = m + 1;
            }
            f[i] = f[id] + 1;
            maximize(res, f[i]);
        }
        cout << res;
    }
}

namespace sub5 {
    int x[N];
    void solve() {
        for(int i = 1; i <= n; ++i) x[i] = inf;
        x[0] = -inf;
        for(int i = 1; i <= n; ++i) {
            int l = 1, r = n, id = 0;
            while(l <= r) {
                int m = (l + r) >> 1;
                if(x[m] >= a[i]) {
                    id = m;
                    r = m - 1;
                }
                else l = m + 1;
            }
            x[id] = a[i];
            maximize(res, id);
        }
        cout << res;
    }
}

namespace sub3 {
    void solve() {
        a[0] = -1;
        for(int i = 1; i <= n; ++i) f[i] = 1;
        for(int i = 1; i <= n; ++i) {
            int id = i + d;
            maximize(res, f[i]);
            for(int j = i + 1; j <= n; ++j) {
                if(a[j] <= a[i]) {
                    id = j + d;
                    continue;
                }
                maximize(f[j], f[i] + 1);
                if(j >= id) break;
            }
        }
        cout << res;
    }
}

struct segtree {
    int st[4 * N];

    segtree() {}

    void update(int id, int l, int r, int i, int v) {
        if(i < l || r < i) return ;
        if(l == r) return void(st[id] = v);
        int m = (l + r) >> 1;
        update(id << 1, l, m, i, v);
        update(id << 1 | 1, m + 1, r, i, v);
        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }

    int walk_left(int id, int l, int r, int v) {
        if(r < v || st[id] == 0) return n + 1;
        if(l == r) return l;
        int m = (l + r) >> 1;
        int res = walk_left(id << 1, l, m, v);
        if(res == n + 1) res = walk_left(id << 1 | 1, m + 1, r, v);
        return res;
    }

    int walk_right(int id, int l, int r, int v) {
        if(v < l || st[id] == 0) return 0;
        if(l == r) return l;
        int m = (l + r) >> 1;
        int res = walk_right(id << 1 | 1, m + 1, r, v);
        if(!res) res = walk_right(id << 1, l, m, v);
        return res;
    }

    int get(int id, int l, int r, int u, int v) {
        if(v < l || r < u) return 0;
        if(l >= u && r <= v) return st[id];
        int m = (l + r) >> 1;
        return max(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
    }

} st[2];

bool cmp(const pii &a, const pii &b) {
    if(a.fi == b.fi) return a.se > b.se;
    return a.fi < b.fi;
}

namespace sub6 {
    void solve() {
        for(int i = 1; i <= n; ++i) b[i] = mp(a[i], i);
        sort(b + 1, b + n + 1);
        s.insert(1);
        for(int i = 1; i <= n; ++i) {
            int id = b[i].se;
            st[0].update(1, 1, n, id, 1);
            int l = st[0].walk_right(1, 1, n, id - 1), r = st[0].walk_left(1, 1, n, id + 1);
            if(s.find(l) != s.end()) s.erase(s.find(l));
            if(id - l > d) s.insert(l);
            if(r - id > d) s.insert(id);
            auto it = s.lower_bound(id);
            if(it == s.end()) lim[id] = n;
            else lim[id] = min(n, (*it) + d);
        }

        for(int i = 1; i <= n; ++i) {
            for(int p : pos[i]) st[1].update(1, 1, n, p, 0);
            int id = lower_bound(b + 1, b + n + 1, mp(a[i], 0)) - b;
            f[i] = st[1].get(1, 1, n, 1, id - 1) + 1;
            maximize(f[i], st[1].get(1, 1, n, id, id + x[a[i]]));
            id += x[a[i]];
            x[a[i]]++;
            st[1].update(1, 1, n, id, f[i]);
            pos[lim[i] + 1].pb(id);
            maximize(res, f[i]);
        }
        cout << res;
    }
}

void solve()
{
//    if(n <= 7000) return void(sub3::solve());
    if(d == 1) return void(sub4::solve());
//    if(d == n) return void(sub5::solve());
    sub6::solve();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	// freopen(file".inp" , "r" , stdin);
	// freopen(file".ans" , "w" , stdout);
    inp();
    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