답안 #46725 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46725	2018-04-22T15:59:00 Z	qoo2p5	Rope (JOI17_rope)	C++17	80 / 100	2500 ms	77972 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];
char bonus[N + 239];

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

void add(int i, int tl, int tr, int ind, int val) {
    if (tl == tr - 1) {
        tree[i] += val;
        return;
    }
    int tm = (tl + tr) / 2;
    if (ind < tm) add(2 * i + 1, tl, tm, ind, val);
    else add(2 * i + 2, tm, tr, ind, val);
    tree[i] = max(tree[2 * i + 1], tree[2 * i + 2]);
}

void add(int ind, int val) {
    add(0, 0, N, ind, val);
}

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 + 1, tl, tm, l, r), get(2 * i + 2, tm, tr, l, r));
}

int get(int l, int r) {
    return get(0, 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, N) {
        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;
            }
            
            rep(who_l, 0, odd_l + 1) {
                rep(who_r, 0, odd_r + 1) {
                    clr();
                    
                    qq++;
                    
                    if (odd_l) {
                        if (who_l) {
                            bonus[a[0]]++;
                        } else {
                            add(a[0], 1);
                        }
                    }
                    if (odd_r) {
                        if (who_r) {
                            bonus[a[n - 1]]++;
                        } else {
                            add(a[n - 1], 1);
                        }
                    }
                    
                    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) {
                        add(i, sz(match[i]) + 2 * cnt_full[i]);
                    }
                    
                    rep(i, 0, m) {
                        int we = bonus[i] + 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[i] > 0) {
                                we--;
                                other++;
                            } else {
                                //~ assert(false);
                            }
                        }
                        
                        mini(ans[i], n - (we + other));
                        
                        for (int j : match[i]) {
                            add(j, 1);
                        }
                    }
                }
            }
        }
    }
    
    assert(qq <= 5);
    
    rep(i, 0, m) {
        cout << ans[i] << "\n";
    }
}

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	42360 KB	Output is correct
2	Correct	72 ms	42472 KB	Output is correct
3	Correct	63 ms	42548 KB	Output is correct
4	Correct	66 ms	42572 KB	Output is correct
5	Correct	69 ms	42572 KB	Output is correct
6	Correct	69 ms	42572 KB	Output is correct
7	Correct	72 ms	42572 KB	Output is correct
8	Correct	66 ms	42624 KB	Output is correct
9	Correct	64 ms	42680 KB	Output is correct
10	Correct	66 ms	42684 KB	Output is correct
11	Correct	72 ms	42684 KB	Output is correct
12	Correct	76 ms	42684 KB	Output is correct
13	Correct	72 ms	42684 KB	Output is correct
14	Correct	64 ms	42684 KB	Output is correct
15	Correct	65 ms	42708 KB	Output is correct
16	Correct	75 ms	42708 KB	Output is correct
17	Correct	69 ms	42712 KB	Output is correct
18	Correct	74 ms	42712 KB	Output is correct
19	Correct	78 ms	42780 KB	Output is correct
20	Correct	73 ms	42780 KB	Output is correct
21	Correct	75 ms	42780 KB	Output is correct
22	Correct	27 ms	42780 KB	Output is correct
23	Correct	63 ms	42788 KB	Output is correct
24	Correct	75 ms	42860 KB	Output is correct
25	Correct	58 ms	42860 KB	Output is correct
26	Correct	21 ms	42860 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	42360 KB	Output is correct
2	Correct	72 ms	42472 KB	Output is correct
3	Correct	63 ms	42548 KB	Output is correct
4	Correct	66 ms	42572 KB	Output is correct
5	Correct	69 ms	42572 KB	Output is correct
6	Correct	69 ms	42572 KB	Output is correct
7	Correct	72 ms	42572 KB	Output is correct
8	Correct	66 ms	42624 KB	Output is correct
9	Correct	64 ms	42680 KB	Output is correct
10	Correct	66 ms	42684 KB	Output is correct
11	Correct	72 ms	42684 KB	Output is correct
12	Correct	76 ms	42684 KB	Output is correct
13	Correct	72 ms	42684 KB	Output is correct
14	Correct	64 ms	42684 KB	Output is correct
15	Correct	65 ms	42708 KB	Output is correct
16	Correct	75 ms	42708 KB	Output is correct
17	Correct	69 ms	42712 KB	Output is correct
18	Correct	74 ms	42712 KB	Output is correct
19	Correct	78 ms	42780 KB	Output is correct
20	Correct	73 ms	42780 KB	Output is correct
21	Correct	75 ms	42780 KB	Output is correct
22	Correct	27 ms	42780 KB	Output is correct
23	Correct	63 ms	42788 KB	Output is correct
24	Correct	75 ms	42860 KB	Output is correct
25	Correct	58 ms	42860 KB	Output is correct
26	Correct	21 ms	42860 KB	Output is correct
27	Correct	200 ms	43644 KB	Output is correct
28	Correct	181 ms	43644 KB	Output is correct
29	Correct	175 ms	43776 KB	Output is correct
30	Correct	153 ms	43776 KB	Output is correct
31	Correct	207 ms	43776 KB	Output is correct
32	Correct	187 ms	43776 KB	Output is correct
33	Correct	170 ms	43776 KB	Output is correct
34	Correct	160 ms	43776 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	42360 KB	Output is correct
2	Correct	72 ms	42472 KB	Output is correct
3	Correct	63 ms	42548 KB	Output is correct
4	Correct	66 ms	42572 KB	Output is correct
5	Correct	69 ms	42572 KB	Output is correct
6	Correct	69 ms	42572 KB	Output is correct
7	Correct	72 ms	42572 KB	Output is correct
8	Correct	66 ms	42624 KB	Output is correct
9	Correct	64 ms	42680 KB	Output is correct
10	Correct	66 ms	42684 KB	Output is correct
11	Correct	72 ms	42684 KB	Output is correct
12	Correct	76 ms	42684 KB	Output is correct
13	Correct	72 ms	42684 KB	Output is correct
14	Correct	64 ms	42684 KB	Output is correct
15	Correct	65 ms	42708 KB	Output is correct
16	Correct	75 ms	42708 KB	Output is correct
17	Correct	69 ms	42712 KB	Output is correct
18	Correct	74 ms	42712 KB	Output is correct
19	Correct	78 ms	42780 KB	Output is correct
20	Correct	73 ms	42780 KB	Output is correct
21	Correct	75 ms	42780 KB	Output is correct
22	Correct	27 ms	42780 KB	Output is correct
23	Correct	63 ms	42788 KB	Output is correct
24	Correct	75 ms	42860 KB	Output is correct
25	Correct	58 ms	42860 KB	Output is correct
26	Correct	21 ms	42860 KB	Output is correct
27	Correct	200 ms	43644 KB	Output is correct
28	Correct	181 ms	43644 KB	Output is correct
29	Correct	175 ms	43776 KB	Output is correct
30	Correct	153 ms	43776 KB	Output is correct
31	Correct	207 ms	43776 KB	Output is correct
32	Correct	187 ms	43776 KB	Output is correct
33	Correct	170 ms	43776 KB	Output is correct
34	Correct	160 ms	43776 KB	Output is correct
35	Correct	245 ms	43776 KB	Output is correct
36	Correct	242 ms	43776 KB	Output is correct
37	Correct	200 ms	43776 KB	Output is correct
38	Correct	214 ms	43776 KB	Output is correct
39	Correct	205 ms	43776 KB	Output is correct
40	Correct	226 ms	43776 KB	Output is correct
41	Correct	233 ms	43776 KB	Output is correct
42	Correct	223 ms	43776 KB	Output is correct
43	Correct	221 ms	43776 KB	Output is correct
44	Correct	236 ms	43776 KB	Output is correct
45	Correct	232 ms	43776 KB	Output is correct
46	Correct	221 ms	43776 KB	Output is correct
47	Correct	235 ms	43776 KB	Output is correct

Subtask #4
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	42360 KB	Output is correct
2	Correct	72 ms	42472 KB	Output is correct
3	Correct	63 ms	42548 KB	Output is correct
4	Correct	66 ms	42572 KB	Output is correct
5	Correct	69 ms	42572 KB	Output is correct
6	Correct	69 ms	42572 KB	Output is correct
7	Correct	72 ms	42572 KB	Output is correct
8	Correct	66 ms	42624 KB	Output is correct
9	Correct	64 ms	42680 KB	Output is correct
10	Correct	66 ms	42684 KB	Output is correct
11	Correct	72 ms	42684 KB	Output is correct
12	Correct	76 ms	42684 KB	Output is correct
13	Correct	72 ms	42684 KB	Output is correct
14	Correct	64 ms	42684 KB	Output is correct
15	Correct	65 ms	42708 KB	Output is correct
16	Correct	75 ms	42708 KB	Output is correct
17	Correct	69 ms	42712 KB	Output is correct
18	Correct	74 ms	42712 KB	Output is correct
19	Correct	78 ms	42780 KB	Output is correct
20	Correct	73 ms	42780 KB	Output is correct
21	Correct	75 ms	42780 KB	Output is correct
22	Correct	27 ms	42780 KB	Output is correct
23	Correct	63 ms	42788 KB	Output is correct
24	Correct	75 ms	42860 KB	Output is correct
25	Correct	58 ms	42860 KB	Output is correct
26	Correct	21 ms	42860 KB	Output is correct
27	Correct	200 ms	43644 KB	Output is correct
28	Correct	181 ms	43644 KB	Output is correct
29	Correct	175 ms	43776 KB	Output is correct
30	Correct	153 ms	43776 KB	Output is correct
31	Correct	207 ms	43776 KB	Output is correct
32	Correct	187 ms	43776 KB	Output is correct
33	Correct	170 ms	43776 KB	Output is correct
34	Correct	160 ms	43776 KB	Output is correct
35	Correct	245 ms	43776 KB	Output is correct
36	Correct	242 ms	43776 KB	Output is correct
37	Correct	200 ms	43776 KB	Output is correct
38	Correct	214 ms	43776 KB	Output is correct
39	Correct	205 ms	43776 KB	Output is correct
40	Correct	226 ms	43776 KB	Output is correct
41	Correct	233 ms	43776 KB	Output is correct
42	Correct	223 ms	43776 KB	Output is correct
43	Correct	221 ms	43776 KB	Output is correct
44	Correct	236 ms	43776 KB	Output is correct
45	Correct	232 ms	43776 KB	Output is correct
46	Correct	221 ms	43776 KB	Output is correct
47	Correct	235 ms	43776 KB	Output is correct
48	Correct	2115 ms	53240 KB	Output is correct
49	Correct	1998 ms	53244 KB	Output is correct
50	Correct	1645 ms	53332 KB	Output is correct
51	Correct	1558 ms	53332 KB	Output is correct
52	Correct	1555 ms	53332 KB	Output is correct
53	Correct	1949 ms	53332 KB	Output is correct
54	Correct	1888 ms	53332 KB	Output is correct
55	Correct	1916 ms	53332 KB	Output is correct
56	Correct	1855 ms	53332 KB	Output is correct

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	42360 KB	Output is correct
2	Correct	72 ms	42472 KB	Output is correct
3	Correct	63 ms	42548 KB	Output is correct
4	Correct	66 ms	42572 KB	Output is correct
5	Correct	69 ms	42572 KB	Output is correct
6	Correct	69 ms	42572 KB	Output is correct
7	Correct	72 ms	42572 KB	Output is correct
8	Correct	66 ms	42624 KB	Output is correct
9	Correct	64 ms	42680 KB	Output is correct
10	Correct	66 ms	42684 KB	Output is correct
11	Correct	72 ms	42684 KB	Output is correct
12	Correct	76 ms	42684 KB	Output is correct
13	Correct	72 ms	42684 KB	Output is correct
14	Correct	64 ms	42684 KB	Output is correct
15	Correct	65 ms	42708 KB	Output is correct
16	Correct	75 ms	42708 KB	Output is correct
17	Correct	69 ms	42712 KB	Output is correct
18	Correct	74 ms	42712 KB	Output is correct
19	Correct	78 ms	42780 KB	Output is correct
20	Correct	73 ms	42780 KB	Output is correct
21	Correct	75 ms	42780 KB	Output is correct
22	Correct	27 ms	42780 KB	Output is correct
23	Correct	63 ms	42788 KB	Output is correct
24	Correct	75 ms	42860 KB	Output is correct
25	Correct	58 ms	42860 KB	Output is correct
26	Correct	21 ms	42860 KB	Output is correct
27	Correct	200 ms	43644 KB	Output is correct
28	Correct	181 ms	43644 KB	Output is correct
29	Correct	175 ms	43776 KB	Output is correct
30	Correct	153 ms	43776 KB	Output is correct
31	Correct	207 ms	43776 KB	Output is correct
32	Correct	187 ms	43776 KB	Output is correct
33	Correct	170 ms	43776 KB	Output is correct
34	Correct	160 ms	43776 KB	Output is correct
35	Correct	245 ms	43776 KB	Output is correct
36	Correct	242 ms	43776 KB	Output is correct
37	Correct	200 ms	43776 KB	Output is correct
38	Correct	214 ms	43776 KB	Output is correct
39	Correct	205 ms	43776 KB	Output is correct
40	Correct	226 ms	43776 KB	Output is correct
41	Correct	233 ms	43776 KB	Output is correct
42	Correct	223 ms	43776 KB	Output is correct
43	Correct	221 ms	43776 KB	Output is correct
44	Correct	236 ms	43776 KB	Output is correct
45	Correct	232 ms	43776 KB	Output is correct
46	Correct	221 ms	43776 KB	Output is correct
47	Correct	235 ms	43776 KB	Output is correct
48	Correct	2115 ms	53240 KB	Output is correct
49	Correct	1998 ms	53244 KB	Output is correct
50	Correct	1645 ms	53332 KB	Output is correct
51	Correct	1558 ms	53332 KB	Output is correct
52	Correct	1555 ms	53332 KB	Output is correct
53	Correct	1949 ms	53332 KB	Output is correct
54	Correct	1888 ms	53332 KB	Output is correct
55	Correct	1916 ms	53332 KB	Output is correct
56	Correct	1855 ms	53332 KB	Output is correct
57	Execution timed out	2562 ms	77972 KB	Time limit exceeded
58	Halted	0 ms	0 KB	-

답안 #46725

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 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
0 / 20.0