답안 #46744 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46744	2018-04-22T16:25:11 Z	qoo2p5	Rope (JOI17_rope)	C++14	100 / 100	2286 ms	102768 KB

rope

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
    if (y < x) {
        x = y;
        return 1;
    }
    return 0;
}

bool maxi(auto &x, const auto &y) {
    if (y > x) {
        x = y;
        return 1;
    }
    return 0;
}

void run();

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    run();
    return 0;
}

const int N = 1 << 20;

int n, m;
int a[N];
int tree[2 * N + 239];
int cnt_full[N + 239];
vector<int> match[N + 239];

void clr() {
    memset(cnt_full, 0, sizeof cnt_full);
    rep(i, 0, m) {
        match[i].clear();
    }
}

void add(int ind, int val) {
    tree[N + ind] += val;
    int i = (N + ind) / 2;
    while (i > 0) {
        tree[i] = max(tree[2 * i], tree[2 * i + 1]);
        i /= 2;
    }
}

int get(int i, int tl, int tr, int l, int r) {
    if (tl >= r || tr <= l) {
        return -INF;
    }
    if (l <= tl && tr <= r) {
        return tree[i];
    }
    int tm = (tl + tr) / 2;
    return max(get(2 * i, tl, tm, l, r), get(2 * i + 1, tm, tr, l, r));
}

int get(int l, int r) {
    return get(1, 0, N, l, r + 1);
}

int ans[N];

void run() {
    cin >> n >> m;
    if (m == 1) {
        cout << "0\n";
        return;
    }
    rep(i, 0, n) {
        cin >> a[i];
        a[i]--;
    }
    rep(i, 0, m) {
        ans[i] = INF;
    }
    
    int qq = 0;
    
    rep(odd_l, 0, 2) {
        rep(odd_r, 0, 2) {
            if ((odd_l + odd_r) % 2 != n % 2) {
                continue;
            }
            
            clr();
            qq++;
            
            for (int i = odd_l; i < n - odd_r; i += 2) {
                if (a[i] != a[i + 1]) {
                    match[a[i]].pb(a[i + 1]);
                    match[a[i + 1]].pb(a[i]);
                } else {
                    cnt_full[a[i]]++;
                }
            }
            
            rep(i, 0, m) {
                tree[N + i] = sz(match[i]) + 2 * cnt_full[i] + (odd_l && a[0] == i) + (odd_r && a[n - 1] == i);
            }
            per(i, N - 1, 1) {
                tree[i] = max(tree[2 * i], tree[2 * i + 1]);
            }
            
            rep(i, 0, m) {
                int bonus = (odd_l && a[0] == i) + (odd_r && a[n - 1] == i);
                int we = bonus + cnt_full[i] * 2;
                int simple = 0;
                for (int j : match[i]) {
                    add(j, -1);
                    we++;
                    simple++;
                }
                
                int other = max(get(0, i - 1), get(i + 1, m - 1));
                assert(other >= 0);
                
                if (other == 0) {
                    if (simple > 0) {
                        we--;
                        other++;
                    } else if (bonus > 0) {
                        we--;
                        other++;
                    } else {
                        //~ assert(false);
                    }
                }
                
                mini(ans[i], n - (we + other));
                
                for (int j : match[i]) {
                    add(j, 1);
                }
            }
        }
    }
    
    assert(qq <= 2);
    
    rep(i, 0, m) {
        cout << ans[i] << "\n";
    }
}

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	33144 KB	Output is correct
2	Correct	30 ms	33252 KB	Output is correct
3	Correct	38 ms	33456 KB	Output is correct
4	Correct	39 ms	33456 KB	Output is correct
5	Correct	39 ms	33456 KB	Output is correct
6	Correct	36 ms	33484 KB	Output is correct
7	Correct	29 ms	33492 KB	Output is correct
8	Correct	39 ms	33492 KB	Output is correct
9	Correct	30 ms	33492 KB	Output is correct
10	Correct	32 ms	33492 KB	Output is correct
11	Correct	31 ms	33492 KB	Output is correct
12	Correct	30 ms	33492 KB	Output is correct
13	Correct	29 ms	33492 KB	Output is correct
14	Correct	30 ms	33492 KB	Output is correct
15	Correct	30 ms	33492 KB	Output is correct
16	Correct	30 ms	33508 KB	Output is correct
17	Correct	30 ms	33508 KB	Output is correct
18	Correct	30 ms	33540 KB	Output is correct
19	Correct	31 ms	33540 KB	Output is correct
20	Correct	31 ms	33540 KB	Output is correct
21	Correct	31 ms	33540 KB	Output is correct
22	Correct	24 ms	33540 KB	Output is correct
23	Correct	30 ms	33540 KB	Output is correct
24	Correct	31 ms	33540 KB	Output is correct
25	Correct	31 ms	33540 KB	Output is correct
26	Correct	20 ms	33540 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	33144 KB	Output is correct
2	Correct	30 ms	33252 KB	Output is correct
3	Correct	38 ms	33456 KB	Output is correct
4	Correct	39 ms	33456 KB	Output is correct
5	Correct	39 ms	33456 KB	Output is correct
6	Correct	36 ms	33484 KB	Output is correct
7	Correct	29 ms	33492 KB	Output is correct
8	Correct	39 ms	33492 KB	Output is correct
9	Correct	30 ms	33492 KB	Output is correct
10	Correct	32 ms	33492 KB	Output is correct
11	Correct	31 ms	33492 KB	Output is correct
12	Correct	30 ms	33492 KB	Output is correct
13	Correct	29 ms	33492 KB	Output is correct
14	Correct	30 ms	33492 KB	Output is correct
15	Correct	30 ms	33492 KB	Output is correct
16	Correct	30 ms	33508 KB	Output is correct
17	Correct	30 ms	33508 KB	Output is correct
18	Correct	30 ms	33540 KB	Output is correct
19	Correct	31 ms	33540 KB	Output is correct
20	Correct	31 ms	33540 KB	Output is correct
21	Correct	31 ms	33540 KB	Output is correct
22	Correct	24 ms	33540 KB	Output is correct
23	Correct	30 ms	33540 KB	Output is correct
24	Correct	31 ms	33540 KB	Output is correct
25	Correct	31 ms	33540 KB	Output is correct
26	Correct	20 ms	33540 KB	Output is correct
27	Correct	65 ms	34428 KB	Output is correct
28	Correct	61 ms	34428 KB	Output is correct
29	Correct	66 ms	34428 KB	Output is correct
30	Correct	63 ms	34428 KB	Output is correct
31	Correct	64 ms	34428 KB	Output is correct
32	Correct	60 ms	34428 KB	Output is correct
33	Correct	65 ms	34432 KB	Output is correct
34	Correct	64 ms	34432 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	33144 KB	Output is correct
2	Correct	30 ms	33252 KB	Output is correct
3	Correct	38 ms	33456 KB	Output is correct
4	Correct	39 ms	33456 KB	Output is correct
5	Correct	39 ms	33456 KB	Output is correct
6	Correct	36 ms	33484 KB	Output is correct
7	Correct	29 ms	33492 KB	Output is correct
8	Correct	39 ms	33492 KB	Output is correct
9	Correct	30 ms	33492 KB	Output is correct
10	Correct	32 ms	33492 KB	Output is correct
11	Correct	31 ms	33492 KB	Output is correct
12	Correct	30 ms	33492 KB	Output is correct
13	Correct	29 ms	33492 KB	Output is correct
14	Correct	30 ms	33492 KB	Output is correct
15	Correct	30 ms	33492 KB	Output is correct
16	Correct	30 ms	33508 KB	Output is correct
17	Correct	30 ms	33508 KB	Output is correct
18	Correct	30 ms	33540 KB	Output is correct
19	Correct	31 ms	33540 KB	Output is correct
20	Correct	31 ms	33540 KB	Output is correct
21	Correct	31 ms	33540 KB	Output is correct
22	Correct	24 ms	33540 KB	Output is correct
23	Correct	30 ms	33540 KB	Output is correct
24	Correct	31 ms	33540 KB	Output is correct
25	Correct	31 ms	33540 KB	Output is correct
26	Correct	20 ms	33540 KB	Output is correct
27	Correct	65 ms	34428 KB	Output is correct
28	Correct	61 ms	34428 KB	Output is correct
29	Correct	66 ms	34428 KB	Output is correct
30	Correct	63 ms	34428 KB	Output is correct
31	Correct	64 ms	34428 KB	Output is correct
32	Correct	60 ms	34428 KB	Output is correct
33	Correct	65 ms	34432 KB	Output is correct
34	Correct	64 ms	34432 KB	Output is correct
35	Correct	66 ms	34556 KB	Output is correct
36	Correct	66 ms	34556 KB	Output is correct
37	Correct	65 ms	34556 KB	Output is correct
38	Correct	66 ms	34556 KB	Output is correct
39	Correct	68 ms	34556 KB	Output is correct
40	Correct	63 ms	34556 KB	Output is correct
41	Correct	62 ms	34556 KB	Output is correct
42	Correct	62 ms	34556 KB	Output is correct
43	Correct	62 ms	34556 KB	Output is correct
44	Correct	63 ms	34556 KB	Output is correct
45	Correct	64 ms	34556 KB	Output is correct
46	Correct	62 ms	34556 KB	Output is correct
47	Correct	65 ms	34556 KB	Output is correct

Subtask #4
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	33144 KB	Output is correct
2	Correct	30 ms	33252 KB	Output is correct
3	Correct	38 ms	33456 KB	Output is correct
4	Correct	39 ms	33456 KB	Output is correct
5	Correct	39 ms	33456 KB	Output is correct
6	Correct	36 ms	33484 KB	Output is correct
7	Correct	29 ms	33492 KB	Output is correct
8	Correct	39 ms	33492 KB	Output is correct
9	Correct	30 ms	33492 KB	Output is correct
10	Correct	32 ms	33492 KB	Output is correct
11	Correct	31 ms	33492 KB	Output is correct
12	Correct	30 ms	33492 KB	Output is correct
13	Correct	29 ms	33492 KB	Output is correct
14	Correct	30 ms	33492 KB	Output is correct
15	Correct	30 ms	33492 KB	Output is correct
16	Correct	30 ms	33508 KB	Output is correct
17	Correct	30 ms	33508 KB	Output is correct
18	Correct	30 ms	33540 KB	Output is correct
19	Correct	31 ms	33540 KB	Output is correct
20	Correct	31 ms	33540 KB	Output is correct
21	Correct	31 ms	33540 KB	Output is correct
22	Correct	24 ms	33540 KB	Output is correct
23	Correct	30 ms	33540 KB	Output is correct
24	Correct	31 ms	33540 KB	Output is correct
25	Correct	31 ms	33540 KB	Output is correct
26	Correct	20 ms	33540 KB	Output is correct
27	Correct	65 ms	34428 KB	Output is correct
28	Correct	61 ms	34428 KB	Output is correct
29	Correct	66 ms	34428 KB	Output is correct
30	Correct	63 ms	34428 KB	Output is correct
31	Correct	64 ms	34428 KB	Output is correct
32	Correct	60 ms	34428 KB	Output is correct
33	Correct	65 ms	34432 KB	Output is correct
34	Correct	64 ms	34432 KB	Output is correct
35	Correct	66 ms	34556 KB	Output is correct
36	Correct	66 ms	34556 KB	Output is correct
37	Correct	65 ms	34556 KB	Output is correct
38	Correct	66 ms	34556 KB	Output is correct
39	Correct	68 ms	34556 KB	Output is correct
40	Correct	63 ms	34556 KB	Output is correct
41	Correct	62 ms	34556 KB	Output is correct
42	Correct	62 ms	34556 KB	Output is correct
43	Correct	62 ms	34556 KB	Output is correct
44	Correct	63 ms	34556 KB	Output is correct
45	Correct	64 ms	34556 KB	Output is correct
46	Correct	62 ms	34556 KB	Output is correct
47	Correct	65 ms	34556 KB	Output is correct
48	Correct	387 ms	44120 KB	Output is correct
49	Correct	383 ms	44284 KB	Output is correct
50	Correct	378 ms	44284 KB	Output is correct
51	Correct	385 ms	44284 KB	Output is correct
52	Correct	378 ms	44284 KB	Output is correct
53	Correct	372 ms	44284 KB	Output is correct
54	Correct	425 ms	44284 KB	Output is correct
55	Correct	362 ms	44284 KB	Output is correct
56	Correct	350 ms	44284 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	33144 KB	Output is correct
2	Correct	30 ms	33252 KB	Output is correct
3	Correct	38 ms	33456 KB	Output is correct
4	Correct	39 ms	33456 KB	Output is correct
5	Correct	39 ms	33456 KB	Output is correct
6	Correct	36 ms	33484 KB	Output is correct
7	Correct	29 ms	33492 KB	Output is correct
8	Correct	39 ms	33492 KB	Output is correct
9	Correct	30 ms	33492 KB	Output is correct
10	Correct	32 ms	33492 KB	Output is correct
11	Correct	31 ms	33492 KB	Output is correct
12	Correct	30 ms	33492 KB	Output is correct
13	Correct	29 ms	33492 KB	Output is correct
14	Correct	30 ms	33492 KB	Output is correct
15	Correct	30 ms	33492 KB	Output is correct
16	Correct	30 ms	33508 KB	Output is correct
17	Correct	30 ms	33508 KB	Output is correct
18	Correct	30 ms	33540 KB	Output is correct
19	Correct	31 ms	33540 KB	Output is correct
20	Correct	31 ms	33540 KB	Output is correct
21	Correct	31 ms	33540 KB	Output is correct
22	Correct	24 ms	33540 KB	Output is correct
23	Correct	30 ms	33540 KB	Output is correct
24	Correct	31 ms	33540 KB	Output is correct
25	Correct	31 ms	33540 KB	Output is correct
26	Correct	20 ms	33540 KB	Output is correct
27	Correct	65 ms	34428 KB	Output is correct
28	Correct	61 ms	34428 KB	Output is correct
29	Correct	66 ms	34428 KB	Output is correct
30	Correct	63 ms	34428 KB	Output is correct
31	Correct	64 ms	34428 KB	Output is correct
32	Correct	60 ms	34428 KB	Output is correct
33	Correct	65 ms	34432 KB	Output is correct
34	Correct	64 ms	34432 KB	Output is correct
35	Correct	66 ms	34556 KB	Output is correct
36	Correct	66 ms	34556 KB	Output is correct
37	Correct	65 ms	34556 KB	Output is correct
38	Correct	66 ms	34556 KB	Output is correct
39	Correct	68 ms	34556 KB	Output is correct
40	Correct	63 ms	34556 KB	Output is correct
41	Correct	62 ms	34556 KB	Output is correct
42	Correct	62 ms	34556 KB	Output is correct
43	Correct	62 ms	34556 KB	Output is correct
44	Correct	63 ms	34556 KB	Output is correct
45	Correct	64 ms	34556 KB	Output is correct
46	Correct	62 ms	34556 KB	Output is correct
47	Correct	65 ms	34556 KB	Output is correct
48	Correct	387 ms	44120 KB	Output is correct
49	Correct	383 ms	44284 KB	Output is correct
50	Correct	378 ms	44284 KB	Output is correct
51	Correct	385 ms	44284 KB	Output is correct
52	Correct	378 ms	44284 KB	Output is correct
53	Correct	372 ms	44284 KB	Output is correct
54	Correct	425 ms	44284 KB	Output is correct
55	Correct	362 ms	44284 KB	Output is correct
56	Correct	350 ms	44284 KB	Output is correct
57	Correct	2286 ms	83500 KB	Output is correct
58	Correct	1733 ms	83500 KB	Output is correct
59	Correct	1721 ms	83500 KB	Output is correct
60	Correct	1918 ms	89660 KB	Output is correct
61	Correct	1894 ms	96424 KB	Output is correct
62	Correct	941 ms	96424 KB	Output is correct
63	Correct	1268 ms	99264 KB	Output is correct
64	Correct	1074 ms	102768 KB	Output is correct
65	Correct	647 ms	102768 KB	Output is correct

답안 #46744

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 30.0 / 30.0

Subtask #3 10.0 / 10.0

Subtask #4 25.0 / 25.0

Subtask #5 20.0 / 20.0

Subtask #1
15.0 / 15.0

Subtask #2
30.0 / 30.0

Subtask #3
10.0 / 10.0

Subtask #4
25.0 / 25.0

Subtask #5
20.0 / 20.0