oj.uz

답안 #940308

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
940308 2024-03-07T07:56:55 Z haxorman Financial Report (JOI21_financial) C++14
19 / 100
 556 ms 43612 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN = 3e5 + 7;
const int SZ = exp2(ceil(log2(mxN)));
const int INF = 1e9 + 7;

int n, d, arr[mxN], seg[4*mxN], dp[mxN], dsu[mxN], lb[mxN];
bool done[mxN];
set<int> inds;
vector<int> pos[mxN];

int find(int x) {
    return dsu[x] < 0 ? x : dsu[x] = find(dsu[x]);
}

void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;

    if (dsu[x] > dsu[y]) {
        swap(x, y);
    }
    dsu[x] += dsu[y];
    dsu[y] = x;
    
    inds.erase(lb[x]);
    inds.erase(lb[y]);
    lb[x] = min(lb[x], lb[y]);

    if (-dsu[x] >= d) {
        inds.insert(lb[x]);
    }
}

void update(int ind, int val) {
    seg[ind+=SZ] = val;
    while (ind /= 2) {
        seg[ind] = max(seg[2*ind], seg[2*ind+1]);
    }
}

int query(int lo, int hi, int ind = 1, int l = 0, int r = SZ - 1) {
    if (lo > r || l > hi) {
        return -INF;
    }

    if (lo <= l && r <= hi) {
        return seg[ind];
    }

    int mid = (l+r)/2;
    return max(query(lo,hi,2*ind,l,mid), query(lo,hi,2*ind+1,mid+1,r));
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> d;
    
    vector<int> vec;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        vec.push_back(arr[i]);
    }
    sort(vec.begin(), vec.end());
    
    int val = 1;
    map<int,int> conv;
    for (int i = 0; i < n; ++i) {
        if (conv.find(vec[i]) == conv.end()) {
            conv[vec[i]] = val++;
        }
    }
    
    vec.clear();
    for (int i = 0; i < n; ++i) {
        arr[i] = conv[arr[i]];

        if (pos[arr[i]].empty()) {
            vec.push_back(arr[i]);
        }
        pos[arr[i]].push_back(i);
        lb[i] = i;

        if (i < n-1) {
            update(i, -INF);
        }
    }
    sort(vec.begin(), vec.end());
    
    inds.insert(n);
    memset(dsu, -1, sizeof(dsu));
    for (int i = vec.size()-1; i >= 0; --i) {
        for (auto x : pos[vec[i]]) {
            int to = *inds.upper_bound(x);

            dp[x] = query(x, min(n-1, to+d-1)) + 1;
        }

        for (auto x : pos[vec[i]]) {
            update(x, dp[x]);

            done[x] = true;
            if (done[x+1]) {
                unite(x,x+1);
            }
            if (x && done[x-1]) {
                unite(x,x-1);
            }
        }
    }

    cout << query(0, n-1) << "\n";
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 4 ms 14936 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16984 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 3 ms 16984 KB Output is correct
12 Correct 4 ms 16988 KB Output is correct
13 Correct 3 ms 16988 KB Output is correct
14 Correct 4 ms 16988 KB Output is correct
15 Correct 3 ms 17032 KB Output is correct
16 Correct 3 ms 16988 KB Output is correct
17 Correct 3 ms 16988 KB Output is correct
18 Correct 3 ms 16988 KB Output is correct
19 Correct 4 ms 16988 KB Output is correct
20 Correct 3 ms 16988 KB Output is correct
21 Correct 3 ms 16988 KB Output is correct
22 Correct 3 ms 16988 KB Output is correct
23 Correct 3 ms 16988 KB Output is correct
24 Correct 3 ms 16984 KB Output is correct
25 Correct 3 ms 16988 KB Output is correct
26 Correct 3 ms 16984 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 4 ms 14936 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16984 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 3 ms 16984 KB Output is correct
12 Correct 4 ms 16988 KB Output is correct
13 Correct 3 ms 16988 KB Output is correct
14 Correct 4 ms 16988 KB Output is correct
15 Correct 3 ms 17032 KB Output is correct
16 Correct 3 ms 16988 KB Output is correct
17 Correct 3 ms 16988 KB Output is correct
18 Correct 3 ms 16988 KB Output is correct
19 Correct 4 ms 16988 KB Output is correct
20 Correct 3 ms 16988 KB Output is correct
21 Correct 3 ms 16988 KB Output is correct
22 Correct 3 ms 16988 KB Output is correct
23 Correct 3 ms 16988 KB Output is correct
24 Correct 3 ms 16984 KB Output is correct
25 Correct 3 ms 16988 KB Output is correct
26 Correct 3 ms 16984 KB Output is correct
27 Incorrect 3 ms 16984 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 4 ms 14936 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16984 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 3 ms 16984 KB Output is correct
12 Correct 4 ms 16988 KB Output is correct
13 Correct 3 ms 16988 KB Output is correct
14 Correct 4 ms 16988 KB Output is correct
15 Correct 3 ms 17032 KB Output is correct
16 Correct 3 ms 16988 KB Output is correct
17 Correct 3 ms 16988 KB Output is correct
18 Correct 3 ms 16988 KB Output is correct
19 Correct 4 ms 16988 KB Output is correct
20 Correct 3 ms 16988 KB Output is correct
21 Correct 3 ms 16988 KB Output is correct
22 Correct 3 ms 16988 KB Output is correct
23 Correct 3 ms 16988 KB Output is correct
24 Correct 3 ms 16984 KB Output is correct
25 Correct 3 ms 16988 KB Output is correct
26 Correct 3 ms 16984 KB Output is correct
27 Incorrect 3 ms 16984 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 21456 KB Output is correct
2 Correct 170 ms 23140 KB Output is correct
3 Incorrect 247 ms 23852 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 139 ms 21324 KB Output is correct
2 Correct 182 ms 21692 KB Output is correct
3 Correct 233 ms 22392 KB Output is correct
4 Correct 506 ms 43448 KB Output is correct
5 Correct 443 ms 43412 KB Output is correct
6 Correct 556 ms 43416 KB Output is correct
7 Correct 255 ms 43592 KB Output is correct
8 Correct 242 ms 43380 KB Output is correct
9 Correct 267 ms 43404 KB Output is correct
10 Correct 335 ms 43356 KB Output is correct
11 Correct 470 ms 43612 KB Output is correct
12 Correct 369 ms 43484 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 4 ms 14936 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16984 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 3 ms 16984 KB Output is correct
12 Correct 4 ms 16988 KB Output is correct
13 Correct 3 ms 16988 KB Output is correct
14 Correct 4 ms 16988 KB Output is correct
15 Correct 3 ms 17032 KB Output is correct
16 Correct 3 ms 16988 KB Output is correct
17 Correct 3 ms 16988 KB Output is correct
18 Correct 3 ms 16988 KB Output is correct
19 Correct 4 ms 16988 KB Output is correct
20 Correct 3 ms 16988 KB Output is correct
21 Correct 3 ms 16988 KB Output is correct
22 Correct 3 ms 16988 KB Output is correct
23 Correct 3 ms 16988 KB Output is correct
24 Correct 3 ms 16984 KB Output is correct
25 Correct 3 ms 16988 KB Output is correct
26 Correct 3 ms 16984 KB Output is correct
27 Incorrect 3 ms 16984 KB Output isn't correct
28 Halted 0 ms 0 KB -