oj.uz

Submission #811957

# Submission time Handle Problem Language Result Execution time Memory
811957 2023-08-07T06:34:40 Z vjudge1 Financial Report (JOI21_financial) C++17
0 / 100
 4000 ms 359108 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = (1 << 19);
const int INF = 1e9;

int n, d;
int a[N];
vector<int> mx(2 * N, -INF);

void update(int pos, int val) {
    for(mx[pos += N] = val; pos > 1; pos >>= 1) {
        mx[pos >> 1] = max(mx[pos], mx[(pos ^ 1)]);
    }
}
// last index i < qr a[i] > val
int left_bound(int qr, int val, int l = 0, int r = N - 1, int v = 1) {
    if(l >= qr || mx[v] <= val)
        return -1;
    if(l == r) 
        return l;
    int m = (l + r) / 2;
    int res = left_bound(qr, val, m + 1, r, 2 * v + 1);
    if(res == -1) res = left_bound(qr, val, l, m, 2 * v);
    return res;
}
// first index i > ql a[i] > val
int right_bound(int ql, int val, int l = 0, int r = N - 1, int v = 1) {
    if(r <= ql || mx[v] <= val)
        return -1;
    if(l == r) 
        return l;
    int m = (l + r) / 2;
    int res = right_bound(ql, val, l, m, 2 * v);
    if(res == -1) res = right_bound(ql, val, m + 1, r, 2 * v + 1);
    return res;
}

void add(int pos) {
    // cout << "add: \n";
    int lb = left_bound(pos, -INF), rb = right_bound(pos, -INF);
    // cout << pos << ' ' << lb << ' ' << rb << '\n';
    if(rb != -1) update(rb, rb - pos);
    update(pos, (lb != -1 ? pos - lb : 0));
}
int get_rb(int pos) {
    int x = right_bound(pos, d);
    if(x == -1) x = n + 1;
    return min(left_bound(x, -INF) + d, n);
}

set<pair<int, int>> st[2 * N];
void insert(int pos, int val, int i) {
    for(pos += N; pos; pos >>= 1) {
        st[pos].insert({val, i});
    }        
}
void erase(int pos, int val, int i) {
    for(pos += N; pos; pos >>= 1) {
        st[pos].erase({val, i});
    }
}
int get(int ql, int qr) {
    int res = 0;
    for(ql += N, qr += N + 1; ql < qr; ql >>= 1, qr >>= 1) {
        if(ql & 1) {
            if(!st[ql].empty())
                res = max(res, (--st[ql].end())->first);
            ql++;
        }
        if(qr & 1) {
            qr--;
            if(!st[qr].empty())
                res = max(res, (--st[qr].end())->first);
        }
    }
    return res;
}
vector<pair<int, int>> cl[N];

void compress() {
    map<int, int> mp;
    for(int i = 1; i <= n; i++) 
        mp[a[i]] = 1;
    int k = 0;
    for(auto &c : mp) 
        c.second = k++;
    for(int i = 1; i <= n; i++) 
        a[i] = mp[a[i]];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> d;
    for(int i = 1; i <= n; i++) 
        cin >> a[i];
    compress();
    vector<pair<int, int>> order;
    for(int i = 1; i <= n; i++) {
        order.push_back({a[i], i});
    }
    int rb[n + 1] = {};
    sort(order.begin(), order.end(), [](pair<int, int> x, pair<int, int> y) {
        if(x.first == y.first) return x.second > y.second;
        return x.first < y.first;
    });
    
    for(auto [a, i] : order) {
        add(i);
        rb[i] = get_rb(i);
    }
    vector<int> dp(n + 1, 1);
    for(int i = 1; i <= n; i++) {
        for(auto [x, val] : cl[i]) 
            erase(x, val, i);
        dp[i] = get(0, a[i] - 1) + 1;
        insert(a[i], dp[i], i);
        cl[rb[i] + 1].push_back({a[i], dp[i]});
    }
    cout << *max_element(dp.begin(), dp.end());
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 65888 KB Output is correct
2 Correct 36 ms 65896 KB Output is correct
3 Correct 41 ms 65872 KB Output is correct
4 Correct 35 ms 65920 KB Output is correct
5 Correct 38 ms 65860 KB Output is correct
6 Correct 39 ms 65992 KB Output is correct
7 Correct 38 ms 65932 KB Output is correct
8 Correct 38 ms 65948 KB Output is correct
9 Correct 36 ms 65880 KB Output is correct
10 Correct 35 ms 65948 KB Output is correct
11 Correct 42 ms 65912 KB Output is correct
12 Incorrect 36 ms 65924 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 65888 KB Output is correct
2 Correct 36 ms 65896 KB Output is correct
3 Correct 41 ms 65872 KB Output is correct
4 Correct 35 ms 65920 KB Output is correct
5 Correct 38 ms 65860 KB Output is correct
6 Correct 39 ms 65992 KB Output is correct
7 Correct 38 ms 65932 KB Output is correct
8 Correct 38 ms 65948 KB Output is correct
9 Correct 36 ms 65880 KB Output is correct
10 Correct 35 ms 65948 KB Output is correct
11 Correct 42 ms 65912 KB Output is correct
12 Incorrect 36 ms 65924 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 65888 KB Output is correct
2 Correct 36 ms 65896 KB Output is correct
3 Correct 41 ms 65872 KB Output is correct
4 Correct 35 ms 65920 KB Output is correct
5 Correct 38 ms 65860 KB Output is correct
6 Correct 39 ms 65992 KB Output is correct
7 Correct 38 ms 65932 KB Output is correct
8 Correct 38 ms 65948 KB Output is correct
9 Correct 36 ms 65880 KB Output is correct
10 Correct 35 ms 65948 KB Output is correct
11 Correct 42 ms 65912 KB Output is correct
12 Incorrect 36 ms 65924 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1811 ms 355964 KB Output is correct
2 Correct 2462 ms 358840 KB Output is correct
3 Incorrect 3868 ms 359108 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1912 ms 355924 KB Output is correct
2 Correct 2992 ms 356004 KB Output is correct
3 Execution timed out 4057 ms 355880 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 65888 KB Output is correct
2 Correct 36 ms 65896 KB Output is correct
3 Correct 41 ms 65872 KB Output is correct
4 Correct 35 ms 65920 KB Output is correct
5 Correct 38 ms 65860 KB Output is correct
6 Correct 39 ms 65992 KB Output is correct
7 Correct 38 ms 65932 KB Output is correct
8 Correct 38 ms 65948 KB Output is correct
9 Correct 36 ms 65880 KB Output is correct
10 Correct 35 ms 65948 KB Output is correct
11 Correct 42 ms 65912 KB Output is correct
12 Incorrect 36 ms 65924 KB Output isn't correct
13 Halted 0 ms 0 KB -