oj.uz

Submission #970950

# Submission time Handle Problem Language Result Execution time Memory
970950 2024-04-27T15:48:35 Z underwaterkillerwhale Financial Report (JOI21_financial) C++17
17 / 100
 558 ms 35768 KB 
#include <bits/stdc++.h>
#define se              second
#define fs              first
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 3e5 + 7;
const ll Mod = 1e9 + 7;
const int szBL = 916;
const int INF = 2e9 + 7;
const int BASE = 137;

int n, D;
int a[N], BoundR[N];
pair<int,int> b[N];
int dp[N];

struct Segment_tree {
    int Range;
    int st[N << 2], lz[N << 2];

    void init (int n) {
        Range = n;
    }

    void down (int id) {
        rep (i, id << 1, id << 1 | 1) {
            lz[i] = max(lz[id], lz[i]);
            st[i] = max(lz[id], st[i]);
        }
        lz[id] = 0;
    }

    void update_Val (int id, int l, int r, int u, int v, int val) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            st[id] = max(st[id], val);
            lz[id] = max(lz[id], val);
            return;
        }
        int mid = l + r >> 1;
        down(id);
        update_Val (id << 1, l, mid, u, v, val);
        update_Val (id << 1 | 1, mid + 1, r, u, v, val);
        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }

    int get_Val (int id, int l, int r, int pos) {
        if (l > pos || r < pos) return 0;
        if (l == r) return st[id];
        int mid = l + r >> 1;
        down(id);
        return max (get_Val(id << 1, l, mid, pos),
                    get_Val (id << 1 | 1 , mid + 1, r, pos) );
    }

    void update_Val (int u, int v, int val) {
        update_Val (1, 1, Range, u, v, val);
    }
    int get_Val (int pos) {
        return get_Val (1, 1, Range, pos);
    }
}ST;

struct DSU {
    int Range;
    int lab[N], sz[N], mx[N];

    void init (int n) {
        rep (i, 1, n) lab[i] = i, sz[i] = 1, mx[i] = i;
    }
    int Find (int u) {
        if (lab[u] == u) return u;
        return lab[u] = Find(lab[u]);
    }
    void Join (int u, int v) {
        u = Find(u);
        v = Find(v);
        if (u == v) return;
        if (sz[u] < sz[v]) swap (u, v);
        lab[v] = u;
        sz[u] += sz[v];
        mx[u] = max(mx[u], mx[v]);
//        cout << u <<" "<<v<<" "<<mx[u] <<" "<<mx[v]<<" hi\n";
    }
}DSU;

void solution () {
    cin >> n >> D;
    rep (i, 1, n) {
        cin >> a[i];
    }
    rep (i, 1, n) b[i] = {a[i], i};
    sort (b + 1, b + 1 + n);
    ST.init(n);
    set<int> S;
    DSU.init(n);
    rep (i, 1, n) {
        if (b[i].fs != b[i - 1].fs) {
            int neo = i;
            while (neo < n && b[neo].fs == b[neo + 1].fs) ++neo;
            rep (j, i, neo) {
                S.insert(b[j].se);
                auto it = S.lower_bound(b[j].se);
                if (it != S.begin()) {
                    if (*it - *prev(it) <= D) {
                        DSU.Join(*it, *prev(it));
                    }
                }
                if (next(it) != S.end()) {
                    if (*next(it) - *it <= D) {
                        DSU.Join(*it, *next(it));
                    }
                }
//                ST.update_Occ (b[j].se, 1);
            }
        }
        int pos = b[i].se;
        dp[pos] = ST.get_Val (pos);
        BoundR[pos] = min(n, DSU.mx[DSU.Find(pos)] + D);
        ST.update_Val (pos, BoundR[pos], dp[pos]);
        if (b[i].fs != b[i + 1].fs) {
            int neo = i;
            while (neo > 1 && b[neo].fs == b[neo - 1].fs) --neo;
            rep (j, neo, i) {
                int pos = b[j].se;
                dp[pos]++;
//                cout << pos <<" "<<dp[pos]<<" "<<BoundR[pos] <<"\n";
                ST.update_Val (pos, BoundR[pos], dp[pos]);
            }
        }
    }

    cout << *max_element (dp + 1, dp + 1 + n) <<"\n";

}

#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);

int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
14 3
74 17 88 80 70 24 66 29 24 63 84 36 72 43

*/

Compilation message

Main.cpp: In member function 'void Segment_tree::update_Val(int, int, int, int, int, int)':
Main.cpp:54:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'int Segment_tree::get_Val(int, int, int, int)':
Main.cpp:64:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Incorrect 2 ms 10588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Incorrect 2 ms 10588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Incorrect 2 ms 10588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 35504 KB Output is correct
2 Correct 266 ms 33500 KB Output is correct
3 Correct 398 ms 35360 KB Output is correct
4 Correct 522 ms 35724 KB Output is correct
5 Correct 363 ms 35412 KB Output is correct
6 Correct 506 ms 35464 KB Output is correct
7 Correct 260 ms 35152 KB Output is correct
8 Correct 249 ms 35384 KB Output is correct
9 Correct 238 ms 35472 KB Output is correct
10 Correct 238 ms 35420 KB Output is correct
11 Correct 335 ms 35356 KB Output is correct
12 Correct 394 ms 35552 KB Output is correct
13 Correct 364 ms 35460 KB Output is correct
14 Correct 558 ms 35768 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 35668 KB Output is correct
2 Correct 411 ms 35092 KB Output is correct
3 Correct 472 ms 35664 KB Output is correct
4 Correct 497 ms 35408 KB Output is correct
5 Correct 414 ms 35412 KB Output is correct
6 Correct 554 ms 35368 KB Output is correct
7 Correct 259 ms 35372 KB Output is correct
8 Correct 244 ms 35412 KB Output is correct
9 Correct 265 ms 35480 KB Output is correct
10 Correct 315 ms 35408 KB Output is correct
11 Correct 526 ms 35412 KB Output is correct
12 Correct 386 ms 35416 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Incorrect 2 ms 10588 KB Output isn't correct
3 Halted 0 ms 0 KB -