답안 #421087

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
421087	2021-06-08T17:37:47 Z	Mamedov	Financial Report (JOI21_financial)	C++17	19 / 100	542 ms	23304 KB

Main

#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define ui unsigned int
#define ull unsigned long long
#define f first
#define s second
#define oo 1000000000

using namespace std;


const int up = 3e5 + 5;
int tree[up << 2];

void update(int node, int l, int r, int pos, int val) {
    if(l == r) {
        tree[node] = val;
    }else {
        int mid = (l + r) >> 1;
        if(pos <= mid) {
            update(node << 1, l, mid, pos, val);
        }else {
            update((node << 1) | 1, mid + 1, r, pos, val);
        }
        tree[node] = max(tree[node << 1], tree[(node << 1) | 1]);
    }
}

int Max(int node, int l, int r, int ql, int qr) {
    if(ql > qr || l > qr || ql > r) return 0;
    if(ql <= l && r <= qr) {
        return tree[node];
    }else {
        int mid = (l + r) >> 1;
        return max(Max(node << 1, l, mid, ql, qr), Max((node << 1) | 1, mid + 1, r, ql, qr));
    }
}

bool cmp(pii p1, pii p2) {
    if(p1.f == p2.f) return p1.s > p2.s;
    else return p1.f < p2.f;
}
void solve() {
    int n, d;
    cin >> n >> d;
    vector<pii>a(n);
    vector<int>dp(n, 1);
    for(int i = 0; i < n; ++i) {
        cin >> a[i].f;
        a[i].s = i;
    }
    set<pii>d_window;
    vector<int>to_left(n);
    to_left[0] = 0;
    d_window.insert(a[0]);
    for(int i = 1; i < n; ++i) {
        auto itr = d_window.upper_bound(a[i]);
        if(itr != d_window.begin()) {
            --itr;
            to_left[i] = to_left[itr->s];
        }else {
            to_left[i] = max(0, i - d);
        }
        if(i - d >= 0) {
            d_window.erase(a[i - d]);
        }
        d_window.insert(a[i]);
    }
    sort(a.begin(), a.end(), cmp);
    int res = 0;
    for(int i = 0; i < n; ++i) {
        int idx = a[i].s;
        dp[idx] = Max(1, 0, n - 1, to_left[idx], idx) + 1;
        update(1, 0, n - 1, idx, dp[idx]);
        //cout << "for " << idx << " " << dp[idx] << '\n';
        res = max(res, dp[idx]);
    }
    cout << res << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	173 ms	9092 KB	Output is correct
2	Correct	203 ms	9116 KB	Output is correct
3	Incorrect	238 ms	9072 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	278 ms	23204 KB	Output is correct
2	Correct	443 ms	23160 KB	Output is correct
3	Correct	531 ms	23256 KB	Output is correct
4	Correct	512 ms	23204 KB	Output is correct
5	Correct	413 ms	23200 KB	Output is correct
6	Correct	509 ms	23304 KB	Output is correct
7	Correct	267 ms	23200 KB	Output is correct
8	Correct	250 ms	23144 KB	Output is correct
9	Correct	244 ms	23156 KB	Output is correct
10	Correct	334 ms	23036 KB	Output is correct
11	Correct	542 ms	23164 KB	Output is correct
12	Correct	392 ms	23232 KB	Output is correct

Subtask #6
0 / 35.0

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

답안 #421087

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 0 / 14.0

Subtask #3 0 / 20.0

Subtask #4 0 / 12.0

Subtask #5 5.0 / 5.0

Subtask #6 0 / 35.0

Subtask #1
14.0 / 14.0

Subtask #2
0 / 14.0

Subtask #3
0 / 20.0

Subtask #4
0 / 12.0

Subtask #5
5.0 / 5.0

Subtask #6
0 / 35.0