oj.uz

Submission #970811

# Submission time Handle Problem Language Result Execution time Memory
970811 2024-04-27T10:24:14 Z underwaterkillerwhale Financial Report (JOI21_financial) C++17
5 / 100
 1225 ms 28244 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;
        rep (i, 1, n << 2) pass[i] = 1;
    }

    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;
            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] && pass[id << 1 | 1] && (Right[id << 1] == 0 || Left[id << 1 | 1] == 0 || 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) {
        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) ST.update_Occ(b[j].se, 1);
        }
        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]++;
//                cout << pos <<" "<<dp[pos]<<" "<<BoundR[pos] <<" "<<ST.get_Bound(7, 9)<<"\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();
}
/*
12 2
26 34 70 37 45 97 53 88 1 68 84 54
26 34 37 45 53 1 68 84
*/

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:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'int Segment_tree::get_Val(int, int, int, int)':
Main.cpp:84:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'int Segment_tree::get_Bound(int, int, int, int, int)':
Main.cpp:93:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function 'int get_Bound(int)':
Main.cpp:114:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |         int mid = lf + rt + 1 >> 1;
      |                   ~~~~~~~~^~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 843 ms 27044 KB Output is correct
2 Correct 894 ms 26204 KB Output is correct
3 Incorrect 1030 ms 28244 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 828 ms 26936 KB Output is correct
2 Correct 981 ms 26456 KB Output is correct
3 Correct 1153 ms 27220 KB Output is correct
4 Correct 1225 ms 26708 KB Output is correct
5 Correct 1103 ms 26856 KB Output is correct
6 Correct 1196 ms 26704 KB Output is correct
7 Correct 853 ms 26448 KB Output is correct
8 Correct 833 ms 26472 KB Output is correct
9 Correct 851 ms 26396 KB Output is correct
10 Correct 1052 ms 26236 KB Output is correct
11 Correct 1155 ms 26908 KB Output is correct
12 Correct 1132 ms 26460 KB Output is correct

Subtask #6
0 / 35.0

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