답안 #46724 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46724	2018-04-22T15:56:20 Z	qoo2p5	Rope (JOI17_rope)	C++17	80 / 100	2500 ms	81208 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 + 15];
int cnt_full[N];
vector<int> match[N];
int bonus[N];

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	60 ms	45432 KB	Output is correct
2	Correct	69 ms	45676 KB	Output is correct
3	Correct	60 ms	45676 KB	Output is correct
4	Correct	61 ms	45676 KB	Output is correct
5	Correct	70 ms	45676 KB	Output is correct
6	Correct	60 ms	45676 KB	Output is correct
7	Correct	68 ms	45676 KB	Output is correct
8	Correct	59 ms	45676 KB	Output is correct
9	Correct	60 ms	45676 KB	Output is correct
10	Correct	59 ms	45676 KB	Output is correct
11	Correct	68 ms	45744 KB	Output is correct
12	Correct	66 ms	45744 KB	Output is correct
13	Correct	78 ms	45804 KB	Output is correct
14	Correct	60 ms	45804 KB	Output is correct
15	Correct	63 ms	45804 KB	Output is correct
16	Correct	67 ms	45804 KB	Output is correct
17	Correct	77 ms	45804 KB	Output is correct
18	Correct	70 ms	45804 KB	Output is correct
19	Correct	70 ms	45804 KB	Output is correct
20	Correct	71 ms	45804 KB	Output is correct
21	Correct	164 ms	45804 KB	Output is correct
22	Correct	21 ms	45804 KB	Output is correct
23	Correct	62 ms	45804 KB	Output is correct
24	Correct	67 ms	45804 KB	Output is correct
25	Correct	66 ms	45804 KB	Output is correct
26	Correct	22 ms	45804 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	60 ms	45432 KB	Output is correct
2	Correct	69 ms	45676 KB	Output is correct
3	Correct	60 ms	45676 KB	Output is correct
4	Correct	61 ms	45676 KB	Output is correct
5	Correct	70 ms	45676 KB	Output is correct
6	Correct	60 ms	45676 KB	Output is correct
7	Correct	68 ms	45676 KB	Output is correct
8	Correct	59 ms	45676 KB	Output is correct
9	Correct	60 ms	45676 KB	Output is correct
10	Correct	59 ms	45676 KB	Output is correct
11	Correct	68 ms	45744 KB	Output is correct
12	Correct	66 ms	45744 KB	Output is correct
13	Correct	78 ms	45804 KB	Output is correct
14	Correct	60 ms	45804 KB	Output is correct
15	Correct	63 ms	45804 KB	Output is correct
16	Correct	67 ms	45804 KB	Output is correct
17	Correct	77 ms	45804 KB	Output is correct
18	Correct	70 ms	45804 KB	Output is correct
19	Correct	70 ms	45804 KB	Output is correct
20	Correct	71 ms	45804 KB	Output is correct
21	Correct	164 ms	45804 KB	Output is correct
22	Correct	21 ms	45804 KB	Output is correct
23	Correct	62 ms	45804 KB	Output is correct
24	Correct	67 ms	45804 KB	Output is correct
25	Correct	66 ms	45804 KB	Output is correct
26	Correct	22 ms	45804 KB	Output is correct
27	Correct	211 ms	46700 KB	Output is correct
28	Correct	183 ms	46700 KB	Output is correct
29	Correct	195 ms	46700 KB	Output is correct
30	Correct	172 ms	46700 KB	Output is correct
31	Correct	223 ms	46700 KB	Output is correct
32	Correct	186 ms	46700 KB	Output is correct
33	Correct	175 ms	46712 KB	Output is correct
34	Correct	165 ms	46712 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	60 ms	45432 KB	Output is correct
2	Correct	69 ms	45676 KB	Output is correct
3	Correct	60 ms	45676 KB	Output is correct
4	Correct	61 ms	45676 KB	Output is correct
5	Correct	70 ms	45676 KB	Output is correct
6	Correct	60 ms	45676 KB	Output is correct
7	Correct	68 ms	45676 KB	Output is correct
8	Correct	59 ms	45676 KB	Output is correct
9	Correct	60 ms	45676 KB	Output is correct
10	Correct	59 ms	45676 KB	Output is correct
11	Correct	68 ms	45744 KB	Output is correct
12	Correct	66 ms	45744 KB	Output is correct
13	Correct	78 ms	45804 KB	Output is correct
14	Correct	60 ms	45804 KB	Output is correct
15	Correct	63 ms	45804 KB	Output is correct
16	Correct	67 ms	45804 KB	Output is correct
17	Correct	77 ms	45804 KB	Output is correct
18	Correct	70 ms	45804 KB	Output is correct
19	Correct	70 ms	45804 KB	Output is correct
20	Correct	71 ms	45804 KB	Output is correct
21	Correct	164 ms	45804 KB	Output is correct
22	Correct	21 ms	45804 KB	Output is correct
23	Correct	62 ms	45804 KB	Output is correct
24	Correct	67 ms	45804 KB	Output is correct
25	Correct	66 ms	45804 KB	Output is correct
26	Correct	22 ms	45804 KB	Output is correct
27	Correct	211 ms	46700 KB	Output is correct
28	Correct	183 ms	46700 KB	Output is correct
29	Correct	195 ms	46700 KB	Output is correct
30	Correct	172 ms	46700 KB	Output is correct
31	Correct	223 ms	46700 KB	Output is correct
32	Correct	186 ms	46700 KB	Output is correct
33	Correct	175 ms	46712 KB	Output is correct
34	Correct	165 ms	46712 KB	Output is correct
35	Correct	248 ms	46716 KB	Output is correct
36	Correct	256 ms	46844 KB	Output is correct
37	Correct	209 ms	46844 KB	Output is correct
38	Correct	221 ms	46844 KB	Output is correct
39	Correct	233 ms	46844 KB	Output is correct
40	Correct	258 ms	46844 KB	Output is correct
41	Correct	242 ms	46844 KB	Output is correct
42	Correct	247 ms	46848 KB	Output is correct
43	Correct	230 ms	46848 KB	Output is correct
44	Correct	239 ms	46848 KB	Output is correct
45	Correct	241 ms	46848 KB	Output is correct
46	Correct	236 ms	46848 KB	Output is correct
47	Correct	241 ms	46848 KB	Output is correct

Subtask #4
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	60 ms	45432 KB	Output is correct
2	Correct	69 ms	45676 KB	Output is correct
3	Correct	60 ms	45676 KB	Output is correct
4	Correct	61 ms	45676 KB	Output is correct
5	Correct	70 ms	45676 KB	Output is correct
6	Correct	60 ms	45676 KB	Output is correct
7	Correct	68 ms	45676 KB	Output is correct
8	Correct	59 ms	45676 KB	Output is correct
9	Correct	60 ms	45676 KB	Output is correct
10	Correct	59 ms	45676 KB	Output is correct
11	Correct	68 ms	45744 KB	Output is correct
12	Correct	66 ms	45744 KB	Output is correct
13	Correct	78 ms	45804 KB	Output is correct
14	Correct	60 ms	45804 KB	Output is correct
15	Correct	63 ms	45804 KB	Output is correct
16	Correct	67 ms	45804 KB	Output is correct
17	Correct	77 ms	45804 KB	Output is correct
18	Correct	70 ms	45804 KB	Output is correct
19	Correct	70 ms	45804 KB	Output is correct
20	Correct	71 ms	45804 KB	Output is correct
21	Correct	164 ms	45804 KB	Output is correct
22	Correct	21 ms	45804 KB	Output is correct
23	Correct	62 ms	45804 KB	Output is correct
24	Correct	67 ms	45804 KB	Output is correct
25	Correct	66 ms	45804 KB	Output is correct
26	Correct	22 ms	45804 KB	Output is correct
27	Correct	211 ms	46700 KB	Output is correct
28	Correct	183 ms	46700 KB	Output is correct
29	Correct	195 ms	46700 KB	Output is correct
30	Correct	172 ms	46700 KB	Output is correct
31	Correct	223 ms	46700 KB	Output is correct
32	Correct	186 ms	46700 KB	Output is correct
33	Correct	175 ms	46712 KB	Output is correct
34	Correct	165 ms	46712 KB	Output is correct
35	Correct	248 ms	46716 KB	Output is correct
36	Correct	256 ms	46844 KB	Output is correct
37	Correct	209 ms	46844 KB	Output is correct
38	Correct	221 ms	46844 KB	Output is correct
39	Correct	233 ms	46844 KB	Output is correct
40	Correct	258 ms	46844 KB	Output is correct
41	Correct	242 ms	46844 KB	Output is correct
42	Correct	247 ms	46848 KB	Output is correct
43	Correct	230 ms	46848 KB	Output is correct
44	Correct	239 ms	46848 KB	Output is correct
45	Correct	241 ms	46848 KB	Output is correct
46	Correct	236 ms	46848 KB	Output is correct
47	Correct	241 ms	46848 KB	Output is correct
48	Correct	1974 ms	56272 KB	Output is correct
49	Correct	1947 ms	56316 KB	Output is correct
50	Correct	1621 ms	56460 KB	Output is correct
51	Correct	1607 ms	56460 KB	Output is correct
52	Correct	1574 ms	56460 KB	Output is correct
53	Correct	1889 ms	56460 KB	Output is correct
54	Correct	1842 ms	56460 KB	Output is correct
55	Correct	1891 ms	56460 KB	Output is correct
56	Correct	1884 ms	56460 KB	Output is correct

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	60 ms	45432 KB	Output is correct
2	Correct	69 ms	45676 KB	Output is correct
3	Correct	60 ms	45676 KB	Output is correct
4	Correct	61 ms	45676 KB	Output is correct
5	Correct	70 ms	45676 KB	Output is correct
6	Correct	60 ms	45676 KB	Output is correct
7	Correct	68 ms	45676 KB	Output is correct
8	Correct	59 ms	45676 KB	Output is correct
9	Correct	60 ms	45676 KB	Output is correct
10	Correct	59 ms	45676 KB	Output is correct
11	Correct	68 ms	45744 KB	Output is correct
12	Correct	66 ms	45744 KB	Output is correct
13	Correct	78 ms	45804 KB	Output is correct
14	Correct	60 ms	45804 KB	Output is correct
15	Correct	63 ms	45804 KB	Output is correct
16	Correct	67 ms	45804 KB	Output is correct
17	Correct	77 ms	45804 KB	Output is correct
18	Correct	70 ms	45804 KB	Output is correct
19	Correct	70 ms	45804 KB	Output is correct
20	Correct	71 ms	45804 KB	Output is correct
21	Correct	164 ms	45804 KB	Output is correct
22	Correct	21 ms	45804 KB	Output is correct
23	Correct	62 ms	45804 KB	Output is correct
24	Correct	67 ms	45804 KB	Output is correct
25	Correct	66 ms	45804 KB	Output is correct
26	Correct	22 ms	45804 KB	Output is correct
27	Correct	211 ms	46700 KB	Output is correct
28	Correct	183 ms	46700 KB	Output is correct
29	Correct	195 ms	46700 KB	Output is correct
30	Correct	172 ms	46700 KB	Output is correct
31	Correct	223 ms	46700 KB	Output is correct
32	Correct	186 ms	46700 KB	Output is correct
33	Correct	175 ms	46712 KB	Output is correct
34	Correct	165 ms	46712 KB	Output is correct
35	Correct	248 ms	46716 KB	Output is correct
36	Correct	256 ms	46844 KB	Output is correct
37	Correct	209 ms	46844 KB	Output is correct
38	Correct	221 ms	46844 KB	Output is correct
39	Correct	233 ms	46844 KB	Output is correct
40	Correct	258 ms	46844 KB	Output is correct
41	Correct	242 ms	46844 KB	Output is correct
42	Correct	247 ms	46848 KB	Output is correct
43	Correct	230 ms	46848 KB	Output is correct
44	Correct	239 ms	46848 KB	Output is correct
45	Correct	241 ms	46848 KB	Output is correct
46	Correct	236 ms	46848 KB	Output is correct
47	Correct	241 ms	46848 KB	Output is correct
48	Correct	1974 ms	56272 KB	Output is correct
49	Correct	1947 ms	56316 KB	Output is correct
50	Correct	1621 ms	56460 KB	Output is correct
51	Correct	1607 ms	56460 KB	Output is correct
52	Correct	1574 ms	56460 KB	Output is correct
53	Correct	1889 ms	56460 KB	Output is correct
54	Correct	1842 ms	56460 KB	Output is correct
55	Correct	1891 ms	56460 KB	Output is correct
56	Correct	1884 ms	56460 KB	Output is correct
57	Execution timed out	2571 ms	81208 KB	Time limit exceeded
58	Halted	0 ms	0 KB	-

답안 #46724

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