oj.uz

답안 #765728

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
765728 2023-06-25T04:12:37 Z joelgun14 Financial Report (JOI21_financial) C++17
5 / 100
 426 ms 98228 KB 
// header file
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// pragma
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// macros
#define endl "\n"
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define lll __int128
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int lim = 1 << 19;
struct segment_tree {
    // fi -> max element
    // se -> index
    priority_queue<pair<int, int>> a[2 * lim];
    void update(int idx, pair<int, int> val) {
        idx += lim;
        while(idx) {
            a[idx].push(val);
            idx >>= 1;
        }
    }
    // find last position dimana max element > k
    int query(int nd, int cl, int cr, int k, int batas) {
        while(a[nd].size() && a[nd].top().se > batas) {
            a[nd].pop();
        }
        if(a[nd].empty() || a[nd].top().fi <= k)
            return -1;
        if(cl == cr)
            return cl;
        int mid = (cl + cr) >> 1;
        int ret = query(2 * nd + 1, mid + 1, cr, k, batas);
        if(ret != -1)
            return ret;
        ret = query(2 * nd, cl, mid, k, batas);
        return ret;
    }
};
int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    int n, d;
    cin >> n >> d;
    int a[n + 1];
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    int ans = 0;
    segment_tree seg;
    for(int i = n; i >= 1; --i) {
        int cur_len = seg.query(1, 0, lim - 1, a[i], i + d);
        if(cur_len == -1)
            ++cur_len;
        seg.update(cur_len + 1, mp(a[i], i));
        ans = max(ans, cur_len + 1);
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 33108 KB Output is correct
2 Correct 20 ms 33148 KB Output is correct
3 Correct 18 ms 33148 KB Output is correct
4 Correct 20 ms 33072 KB Output is correct
5 Correct 18 ms 33148 KB Output is correct
6 Correct 20 ms 33228 KB Output is correct
7 Correct 18 ms 33108 KB Output is correct
8 Correct 18 ms 33092 KB Output is correct
9 Correct 20 ms 33236 KB Output is correct
10 Correct 18 ms 33108 KB Output is correct
11 Correct 18 ms 33124 KB Output is correct
12 Correct 18 ms 33108 KB Output is correct
13 Correct 20 ms 33152 KB Output is correct
14 Correct 18 ms 33108 KB Output is correct
15 Incorrect 18 ms 33144 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 33108 KB Output is correct
2 Correct 20 ms 33148 KB Output is correct
3 Correct 18 ms 33148 KB Output is correct
4 Correct 20 ms 33072 KB Output is correct
5 Correct 18 ms 33148 KB Output is correct
6 Correct 20 ms 33228 KB Output is correct
7 Correct 18 ms 33108 KB Output is correct
8 Correct 18 ms 33092 KB Output is correct
9 Correct 20 ms 33236 KB Output is correct
10 Correct 18 ms 33108 KB Output is correct
11 Correct 18 ms 33124 KB Output is correct
12 Correct 18 ms 33108 KB Output is correct
13 Correct 20 ms 33152 KB Output is correct
14 Correct 18 ms 33108 KB Output is correct
15 Incorrect 18 ms 33144 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 33108 KB Output is correct
2 Correct 20 ms 33148 KB Output is correct
3 Correct 18 ms 33148 KB Output is correct
4 Correct 20 ms 33072 KB Output is correct
5 Correct 18 ms 33148 KB Output is correct
6 Correct 20 ms 33228 KB Output is correct
7 Correct 18 ms 33108 KB Output is correct
8 Correct 18 ms 33092 KB Output is correct
9 Correct 20 ms 33236 KB Output is correct
10 Correct 18 ms 33108 KB Output is correct
11 Correct 18 ms 33124 KB Output is correct
12 Correct 18 ms 33108 KB Output is correct
13 Correct 20 ms 33152 KB Output is correct
14 Correct 18 ms 33108 KB Output is correct
15 Incorrect 18 ms 33144 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 82588 KB Output is correct
2 Incorrect 426 ms 43024 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 84724 KB Output is correct
2 Correct 263 ms 87788 KB Output is correct
3 Correct 278 ms 89436 KB Output is correct
4 Correct 277 ms 89832 KB Output is correct
5 Correct 310 ms 98228 KB Output is correct
6 Correct 280 ms 90768 KB Output is correct
7 Correct 195 ms 95952 KB Output is correct
8 Correct 330 ms 84420 KB Output is correct
9 Correct 173 ms 92828 KB Output is correct
10 Correct 195 ms 90212 KB Output is correct
11 Correct 307 ms 90820 KB Output is correct
12 Correct 202 ms 89312 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 33108 KB Output is correct
2 Correct 20 ms 33148 KB Output is correct
3 Correct 18 ms 33148 KB Output is correct
4 Correct 20 ms 33072 KB Output is correct
5 Correct 18 ms 33148 KB Output is correct
6 Correct 20 ms 33228 KB Output is correct
7 Correct 18 ms 33108 KB Output is correct
8 Correct 18 ms 33092 KB Output is correct
9 Correct 20 ms 33236 KB Output is correct
10 Correct 18 ms 33108 KB Output is correct
11 Correct 18 ms 33124 KB Output is correct
12 Correct 18 ms 33108 KB Output is correct
13 Correct 20 ms 33152 KB Output is correct
14 Correct 18 ms 33108 KB Output is correct
15 Incorrect 18 ms 33144 KB Output isn't correct
16 Halted 0 ms 0 KB -