oj.uz

Submission #421322

# Submission time Handle Problem Language Result Execution time Memory
421322 2021-06-09T02:52:01 Z kwongweng Financial Report (JOI21_financial) C++17
5 / 100
 280 ms 12132 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define ms memset
#define fi first
#define se second

ll MOD = 1000000007;
ll A = 998244353;

ll power(ll base, ll n){
    if (n == 0) return 1;
    if (n == 1) return base;
    ll halfn = power(base, n/2);
    if (n%2 == 0) return (halfn*halfn)%MOD;
    return (((halfn*halfn)%MOD)*base) % MOD;
}

ll inverse(ll n){
    return power(n, MOD-2);
}

ll add(ll a, ll b){
    return (a+b) % MOD;
}

ll mul(ll a, ll b){
    return (a*b) % MOD;
}

ll gcd(ll a, ll b){
    if (a == 0) return b;
    if (a == 1) return 1;
    return gcd(b%a, a);
}

struct segtree{
    int sz; vi mini;
    void init(int n){
        sz = n;
        mini.assign(4*n, 0);
    }
    void update(int v, int tl, int tr, int pos, int val){
        if (tl == tr){
            mini[v] = val;
            return;
        }
        int tm = (tl + tr)/2;
        if (pos <= tm){
            update(2*v, tl, tm, pos, val);
        }else{
            update(2*v+1, tm+1, tr, pos, val);
        }
        mini[v] = max(mini[2*v], mini[2*v+1]);
    }
    void update(int pos, int val){
        update(1, 0, sz-1, pos, val);
    }
    int get(int v, int tl, int tr, int l, int r){
        if (tl == l && tr == r) return mini[v];
        if (l > r) return 0;
        int tm = (tl + tr)/2;
        return max(get(2*v, tl, tm, l, min(r, tm)), get(2*v+1, tm+1, tr, max(l, tm+1), r));
    }
    int get(int l, int r){
        return get(1, 0, sz-1, l, r);
    }
};
int n, d;
const int N = 300000;
vi p(N);
set<int> st;
int get(int a){
    if (p[a] == a) return a;
    p[a] = get(p[a]);
    return p[a];
}

void add(int a){
    auto it = st.upper_bound(a);
    int b = *it;
    if (it != st.end()){
        if (b - a <= d) p[a] = b;
    }
    if (it != st.begin()){
        --it;
        b = *it;
        if (a - b <= d) p[b] = a;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin >> n >> d;
    vi a(n); FOR(i, 0, n) cin >> a[i];
    vii b(n); FOR(i, 0, n) b[i] = {a[i], i};
    sort(b.begin(), b.end());
    vi r(n);
    FOR(i, 0, n) p[i] = i;
    for (int i = 0; i < n;){
        int j = i;
        while (j < n && b[j].fi == b[i].fi){
            add(b[j].se);
            j++;
        }
        while (i < j){
            r[b[i].se] = get(b[i].se) + d;
            i++;
        }
    }
    int maxi = 1;
    segtree st;
    st.init(n);
    vi dp(n);
    for (int i = n-1; i >= 0;){
        int j = i;
        while (j >= 0 && b[j].fi == b[i].fi){
            int k = b[j].se; r[k] = min(r[k], n-1);
            dp[k] = st.get(k, r[k]) + 1;
            maxi = max(maxi, dp[k]);
            j--;
        }
        while (i > j){
            int k = b[i].se;
            st.update(k, dp[k]);
            i--;
        }
    }
    cout << maxi << '\n';
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 1 ms 1432 KB Output is correct
8 Correct 1 ms 1484 KB Output is correct
9 Correct 1 ms 1484 KB Output is correct
10 Correct 1 ms 1484 KB Output is correct
11 Correct 1 ms 1484 KB Output is correct
12 Correct 1 ms 1484 KB Output is correct
13 Correct 1 ms 1484 KB Output is correct
14 Correct 1 ms 1484 KB Output is correct
15 Incorrect 1 ms 1428 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 1 ms 1432 KB Output is correct
8 Correct 1 ms 1484 KB Output is correct
9 Correct 1 ms 1484 KB Output is correct
10 Correct 1 ms 1484 KB Output is correct
11 Correct 1 ms 1484 KB Output is correct
12 Correct 1 ms 1484 KB Output is correct
13 Correct 1 ms 1484 KB Output is correct
14 Correct 1 ms 1484 KB Output is correct
15 Incorrect 1 ms 1428 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 1 ms 1432 KB Output is correct
8 Correct 1 ms 1484 KB Output is correct
9 Correct 1 ms 1484 KB Output is correct
10 Correct 1 ms 1484 KB Output is correct
11 Correct 1 ms 1484 KB Output is correct
12 Correct 1 ms 1484 KB Output is correct
13 Correct 1 ms 1484 KB Output is correct
14 Correct 1 ms 1484 KB Output is correct
15 Incorrect 1 ms 1428 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 12048 KB Output is correct
2 Incorrect 170 ms 12048 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 145 ms 12044 KB Output is correct
2 Correct 211 ms 12016 KB Output is correct
3 Correct 234 ms 11972 KB Output is correct
4 Correct 275 ms 12048 KB Output is correct
5 Correct 226 ms 12132 KB Output is correct
6 Correct 247 ms 12040 KB Output is correct
7 Correct 163 ms 11996 KB Output is correct
8 Correct 145 ms 12008 KB Output is correct
9 Correct 142 ms 11992 KB Output is correct
10 Correct 181 ms 12012 KB Output is correct
11 Correct 280 ms 12012 KB Output is correct
12 Correct 189 ms 12048 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 1 ms 1484 KB Output is correct
7 Correct 1 ms 1432 KB Output is correct
8 Correct 1 ms 1484 KB Output is correct
9 Correct 1 ms 1484 KB Output is correct
10 Correct 1 ms 1484 KB Output is correct
11 Correct 1 ms 1484 KB Output is correct
12 Correct 1 ms 1484 KB Output is correct
13 Correct 1 ms 1484 KB Output is correct
14 Correct 1 ms 1484 KB Output is correct
15 Incorrect 1 ms 1428 KB Output isn't correct
16 Halted 0 ms 0 KB -