oj.uz

Submission #970783

# Submission time Handle Problem Language Result Execution time Memory
970783 2024-04-27T08:55:22 Z underwaterkillerwhale Financial Report (JOI21_financial) C++17
5 / 100
 1099 ms 18980 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 Right[N << 2], Left[N << 2];
    int st[N << 2], lz[N << 2];
    bool pass[N << 2]; /// go to the leftmost

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

    void update_Occ (int id, int l, int r, int pos, int val) {
        if (l > pos || r < pos) return;
        if (l == r) {
            Left[id] = pos;
            Right[id] = pos;
            pass[id] = 1;
            return;
        }
        int mid = l + r >> 1;
        update_Occ (id << 1, l, mid, pos, val);
        update_Occ (id << 1 | 1, mid + 1, r, pos, val);
        if (pass[id << 1 | 1] && pass[id << 1] && Left[id << 1 | 1] - Right[id << 1] <= D)  pass[id] = 1;
        else pass[id] = 0;
        Left[id] = Left[id << 1];
        Right[id] = Right[id << 1 | 1];
    }

    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) );
    }

    int get_Bound (int id, int l, int r, int u, int v) {
        if (l > v || r < u) return 1;
        if (l >= u && r <= v) return pass[id];
        int mid = l + r >> 1;
        return min (get_Bound (id << 1, l, mid, u, v),
                    get_Bound (id << 1 | 1 , mid + 1, r, u, v) );
    }
    void update_Occ (int pos, int val) {
        update_Occ (1, 1, Range, pos, val);
    }
    void update_Val (int u, int v, int val) {
        update_Val (1, 1, Range, u, v, val);
    }
    int get_Bound (int u, int v) {
        return get_Bound (1, 1, Range, u, v);
    }
    int get_Val (int pos) {
        return get_Val (1, 1, Range, pos);
    }
}ST;

int get_Bound (int pos) {
    int lf = pos, rt = n;
    while (lf < rt) {
        int mid = lf + rt + 1 >> 1;
        if (ST.get_Bound(pos, mid)) lf = mid;
        else rt = mid - 1;
    }
    return rt;
}

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);
    rep (i, 1, n) {
        int pos = b[i].se;
        dp[pos] = ST.get_Val (pos);
        BoundR[pos] = min(n, get_Bound (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]++;
                ST.update_Val (pos, BoundR[pos], dp[pos]);
            }
        }
    }
    int res = dp[n];
    rep (i, 1, n) if (a[i] >= a[n]) res = max(res, dp[i]);
    cout << res <<"\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();
}
/*
7 1
100 600 600 200 300 500 500
*/

Compilation message

Main.cpp: In member function 'void Segment_tree::update_Occ(int, int, int, int, int)':
Main.cpp:49:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void Segment_tree::update_Val(int, int, int, int, int, int)':
Main.cpp:73:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'int Segment_tree::get_Val(int, int, int, int)':
Main.cpp:83:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'int Segment_tree::get_Bound(int, int, int, int, int)':
Main.cpp:92:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function 'int get_Bound(int)':
Main.cpp:113:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 |         int mid = lf + rt + 1 >> 1;
      |                   ~~~~~~~~^~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 776 ms 18628 KB Output is correct
2 Incorrect 855 ms 18428 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 773 ms 18952 KB Output is correct
2 Correct 943 ms 18720 KB Output is correct
3 Correct 1069 ms 18760 KB Output is correct
4 Correct 1046 ms 17488 KB Output is correct
5 Correct 987 ms 17436 KB Output is correct
6 Correct 1099 ms 18768 KB Output is correct
7 Correct 759 ms 18808 KB Output is correct
8 Correct 765 ms 17328 KB Output is correct
9 Correct 792 ms 18980 KB Output is correct
10 Correct 1020 ms 18628 KB Output is correct
11 Correct 1089 ms 17432 KB Output is correct
12 Correct 1025 ms 18688 KB Output is correct

Subtask #6
0 / 35.0

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