oj.uz

Submission #173188

# Submission time Handle Problem Language Result Execution time Memory
173188 2020-01-03T14:41:42 Z mhy908 Rope (JOI17_rope) C++14
100 / 100
 2350 ms 58960 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=9000000000000000000;
const int inf=2000000000;
const LL hashnum=100000000;
int n, m;
int arr[1000010];
int cnt[1000010], cnt2[1000010];
vector<pii> q;
struct SEGMENT_TREE
{
    int initial=-inf;
    int x;
    struct NODE{
        int st, fin;
        int q;
    }tree[4000000];
    int f(int a, int b){return max(a, b);}
    void init(int point, int num){
        if(num==1)tree[point].st=tree[point].fin=++x;
        if(num<=1)return;
        init(point*2, num-num/2);
        init(point*2+1, num/2);
        tree[point].st=tree[point*2].st;
        tree[point].fin=tree[point*2+1].fin;
    }
    void cl(int point){
        tree[point].q=0;
        if(tree[point].st==tree[point].fin)return;
        cl(point*2);
        cl(point*2+1);
    }
    void update(int point, int num, int qu){
        if(tree[point].st==tree[point].fin){
            tree[point].q+=qu;
            return;
        }
        if(num<=tree[point*2].fin)update(point*2, num, qu);
        else update(point*2+1, num, qu);
        tree[point].q=f(tree[point*2].q, tree[point*2+1].q);
    }
    int query(int point, int a, int b){
        if(tree[point].st>=a&&tree[point].fin<=b)return tree[point].q;
        if(tree[point].st>b||tree[point].fin<a)return initial;
        return f(query(point*2, a, b), query(point*2+1, a, b));
    }
    void init(int num){init(1, num);}
    void update(int num, LL qu){update(1, num, qu);}
    void cl(){cl(1);}
    int query(int a, int b){return query(1, a, b);}
}seg;
int ans[1000010];
int main()
{
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i]);
        if(i%2==0){
            if(arr[i-1]!=arr[i]){
                q.pb(mp(arr[i], arr[i-1]));
                q.pb(mp(arr[i-1], arr[i]));
                cnt[arr[i]]++;
                cnt[arr[i-1]]++;
            }
            else{
                cnt2[arr[i]]+=2;
            }
        }
        if(n%2&&i==n){
            cnt2[arr[i]]++;
        }
    }
    sort(all(q));
    seg.init(m);
    for(int i=1; i<=m; i++){
        seg.update(i, cnt[i]+cnt2[i]);
        ans[i]=inf;
    }
    int pv=0;
    for(int i=1; i<=m; i++){
        int temppv=pv;
        seg.update(i, -cnt[i]-cnt2[i]);
        for(; pv<q.size(); pv++){
            if(q[pv].F!=i)break;
            seg.update(q[pv].S, -1);
        }
        int turna=cnt[i];
        int turnb=n-cnt[i]*2-cnt2[i]-seg.query(1, m);
        ans[i]=min(ans[i], turna+turnb);
        seg.update(i, cnt[i]+cnt2[i]);
        for(; temppv<pv; temppv++){
            seg.update(q[temppv].S, 1);
        }
    }
    seg.cl();
    memset(cnt, 0, sizeof(cnt));
    memset(cnt2, 0, sizeof(cnt2));
    q.clear();
    for(int i=1; i<=n; i++){
        if(i==1){
            cnt2[arr[i]]++;
        }
        else if(i%2){
            if(arr[i-1]!=arr[i]){
                q.pb(mp(arr[i], arr[i-1]));
                q.pb(mp(arr[i-1], arr[i]));
                cnt[arr[i]]++;
                cnt[arr[i-1]]++;
            }
            else{
                cnt2[arr[i]]+=2;
            }
        }
        if(n%2==0&&i==n){
            cnt2[arr[i]]++;
        }
    }
    sort(all(q));
    for(int i=1; i<=m; i++)seg.update(i, cnt[i]+cnt2[i]);
    pv=0;
    for(int i=1; i<=m; i++){
        int temppv=pv;
        seg.update(i, -cnt[i]-cnt2[i]);
        for(; pv<q.size(); pv++){
            if(q[pv].F!=i)break;
            seg.update(q[pv].S, -1);
        }
        int turna=cnt[i];
        int turnb=n-cnt[i]*2-cnt2[i]-seg.query(1, m);
        ans[i]=min(ans[i], turna+turnb);
        seg.update(i, cnt[i]+cnt2[i]);
        for(; temppv<pv; temppv++){
            seg.update(q[temppv].S, 1);
        }
    }
    for(int i=1; i<=m; i++){
        printf("%d\n", ans[i]);
    }
}

Compilation message

rope.cpp: In function 'int main()':
rope.cpp:91:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; pv<q.size(); pv++){
               ~~^~~~~~~~~
rope.cpp:132:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; pv<q.size(); pv++){
               ~~^~~~~~~~~
rope.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
rope.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8284 KB Output is correct
2 Correct 8 ms 8184 KB Output is correct
3 Correct 8 ms 8184 KB Output is correct
4 Correct 8 ms 8184 KB Output is correct
5 Correct 8 ms 8184 KB Output is correct
6 Correct 8 ms 8184 KB Output is correct
7 Correct 8 ms 8156 KB Output is correct
8 Correct 8 ms 8136 KB Output is correct
9 Correct 8 ms 8184 KB Output is correct
10 Correct 8 ms 8184 KB Output is correct
11 Correct 8 ms 8184 KB Output is correct
12 Correct 8 ms 8188 KB Output is correct
13 Correct 8 ms 8188 KB Output is correct
14 Correct 8 ms 8184 KB Output is correct
15 Correct 8 ms 8184 KB Output is correct
16 Correct 8 ms 8196 KB Output is correct
17 Correct 8 ms 8184 KB Output is correct
18 Correct 8 ms 8184 KB Output is correct
19 Correct 8 ms 8184 KB Output is correct
20 Correct 8 ms 8180 KB Output is correct
21 Correct 8 ms 8184 KB Output is correct
22 Correct 8 ms 8184 KB Output is correct
23 Correct 8 ms 8184 KB Output is correct
24 Correct 8 ms 8184 KB Output is correct
25 Correct 8 ms 8204 KB Output is correct
26 Correct 8 ms 8184 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8284 KB Output is correct
2 Correct 8 ms 8184 KB Output is correct
3 Correct 8 ms 8184 KB Output is correct
4 Correct 8 ms 8184 KB Output is correct
5 Correct 8 ms 8184 KB Output is correct
6 Correct 8 ms 8184 KB Output is correct
7 Correct 8 ms 8156 KB Output is correct
8 Correct 8 ms 8136 KB Output is correct
9 Correct 8 ms 8184 KB Output is correct
10 Correct 8 ms 8184 KB Output is correct
11 Correct 8 ms 8184 KB Output is correct
12 Correct 8 ms 8188 KB Output is correct
13 Correct 8 ms 8188 KB Output is correct
14 Correct 8 ms 8184 KB Output is correct
15 Correct 8 ms 8184 KB Output is correct
16 Correct 8 ms 8196 KB Output is correct
17 Correct 8 ms 8184 KB Output is correct
18 Correct 8 ms 8184 KB Output is correct
19 Correct 8 ms 8184 KB Output is correct
20 Correct 8 ms 8180 KB Output is correct
21 Correct 8 ms 8184 KB Output is correct
22 Correct 8 ms 8184 KB Output is correct
23 Correct 8 ms 8184 KB Output is correct
24 Correct 8 ms 8184 KB Output is correct
25 Correct 8 ms 8204 KB Output is correct
26 Correct 8 ms 8184 KB Output is correct
27 Correct 34 ms 9576 KB Output is correct
28 Correct 29 ms 9452 KB Output is correct
29 Correct 35 ms 9576 KB Output is correct
30 Correct 30 ms 9540 KB Output is correct
31 Correct 35 ms 9552 KB Output is correct
32 Correct 29 ms 9480 KB Output is correct
33 Correct 35 ms 9580 KB Output is correct
34 Correct 30 ms 9548 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8284 KB Output is correct
2 Correct 8 ms 8184 KB Output is correct
3 Correct 8 ms 8184 KB Output is correct
4 Correct 8 ms 8184 KB Output is correct
5 Correct 8 ms 8184 KB Output is correct
6 Correct 8 ms 8184 KB Output is correct
7 Correct 8 ms 8156 KB Output is correct
8 Correct 8 ms 8136 KB Output is correct
9 Correct 8 ms 8184 KB Output is correct
10 Correct 8 ms 8184 KB Output is correct
11 Correct 8 ms 8184 KB Output is correct
12 Correct 8 ms 8188 KB Output is correct
13 Correct 8 ms 8188 KB Output is correct
14 Correct 8 ms 8184 KB Output is correct
15 Correct 8 ms 8184 KB Output is correct
16 Correct 8 ms 8196 KB Output is correct
17 Correct 8 ms 8184 KB Output is correct
18 Correct 8 ms 8184 KB Output is correct
19 Correct 8 ms 8184 KB Output is correct
20 Correct 8 ms 8180 KB Output is correct
21 Correct 8 ms 8184 KB Output is correct
22 Correct 8 ms 8184 KB Output is correct
23 Correct 8 ms 8184 KB Output is correct
24 Correct 8 ms 8184 KB Output is correct
25 Correct 8 ms 8204 KB Output is correct
26 Correct 8 ms 8184 KB Output is correct
27 Correct 34 ms 9576 KB Output is correct
28 Correct 29 ms 9452 KB Output is correct
29 Correct 35 ms 9576 KB Output is correct
30 Correct 30 ms 9540 KB Output is correct
31 Correct 35 ms 9552 KB Output is correct
32 Correct 29 ms 9480 KB Output is correct
33 Correct 35 ms 9580 KB Output is correct
34 Correct 30 ms 9548 KB Output is correct
35 Correct 65 ms 9676 KB Output is correct
36 Correct 64 ms 9708 KB Output is correct
37 Correct 64 ms 9708 KB Output is correct
38 Correct 64 ms 9836 KB Output is correct
39 Correct 64 ms 9708 KB Output is correct
40 Correct 58 ms 9836 KB Output is correct
41 Correct 59 ms 9712 KB Output is correct
42 Correct 56 ms 9864 KB Output is correct
43 Correct 54 ms 9704 KB Output is correct
44 Correct 58 ms 9708 KB Output is correct
45 Correct 59 ms 9768 KB Output is correct
46 Correct 56 ms 9872 KB Output is correct
47 Correct 55 ms 9704 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8284 KB Output is correct
2 Correct 8 ms 8184 KB Output is correct
3 Correct 8 ms 8184 KB Output is correct
4 Correct 8 ms 8184 KB Output is correct
5 Correct 8 ms 8184 KB Output is correct
6 Correct 8 ms 8184 KB Output is correct
7 Correct 8 ms 8156 KB Output is correct
8 Correct 8 ms 8136 KB Output is correct
9 Correct 8 ms 8184 KB Output is correct
10 Correct 8 ms 8184 KB Output is correct
11 Correct 8 ms 8184 KB Output is correct
12 Correct 8 ms 8188 KB Output is correct
13 Correct 8 ms 8188 KB Output is correct
14 Correct 8 ms 8184 KB Output is correct
15 Correct 8 ms 8184 KB Output is correct
16 Correct 8 ms 8196 KB Output is correct
17 Correct 8 ms 8184 KB Output is correct
18 Correct 8 ms 8184 KB Output is correct
19 Correct 8 ms 8184 KB Output is correct
20 Correct 8 ms 8180 KB Output is correct
21 Correct 8 ms 8184 KB Output is correct
22 Correct 8 ms 8184 KB Output is correct
23 Correct 8 ms 8184 KB Output is correct
24 Correct 8 ms 8184 KB Output is correct
25 Correct 8 ms 8204 KB Output is correct
26 Correct 8 ms 8184 KB Output is correct
27 Correct 34 ms 9576 KB Output is correct
28 Correct 29 ms 9452 KB Output is correct
29 Correct 35 ms 9576 KB Output is correct
30 Correct 30 ms 9540 KB Output is correct
31 Correct 35 ms 9552 KB Output is correct
32 Correct 29 ms 9480 KB Output is correct
33 Correct 35 ms 9580 KB Output is correct
34 Correct 30 ms 9548 KB Output is correct
35 Correct 65 ms 9676 KB Output is correct
36 Correct 64 ms 9708 KB Output is correct
37 Correct 64 ms 9708 KB Output is correct
38 Correct 64 ms 9836 KB Output is correct
39 Correct 64 ms 9708 KB Output is correct
40 Correct 58 ms 9836 KB Output is correct
41 Correct 59 ms 9712 KB Output is correct
42 Correct 56 ms 9864 KB Output is correct
43 Correct 54 ms 9704 KB Output is correct
44 Correct 58 ms 9708 KB Output is correct
45 Correct 59 ms 9768 KB Output is correct
46 Correct 56 ms 9872 KB Output is correct
47 Correct 55 ms 9704 KB Output is correct
48 Correct 721 ms 22040 KB Output is correct
49 Correct 719 ms 20472 KB Output is correct
50 Correct 718 ms 21580 KB Output is correct
51 Correct 650 ms 24372 KB Output is correct
52 Correct 599 ms 23792 KB Output is correct
53 Correct 644 ms 21896 KB Output is correct
54 Correct 613 ms 20476 KB Output is correct
55 Correct 607 ms 20448 KB Output is correct
56 Correct 589 ms 20748 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8284 KB Output is correct
2 Correct 8 ms 8184 KB Output is correct
3 Correct 8 ms 8184 KB Output is correct
4 Correct 8 ms 8184 KB Output is correct
5 Correct 8 ms 8184 KB Output is correct
6 Correct 8 ms 8184 KB Output is correct
7 Correct 8 ms 8156 KB Output is correct
8 Correct 8 ms 8136 KB Output is correct
9 Correct 8 ms 8184 KB Output is correct
10 Correct 8 ms 8184 KB Output is correct
11 Correct 8 ms 8184 KB Output is correct
12 Correct 8 ms 8188 KB Output is correct
13 Correct 8 ms 8188 KB Output is correct
14 Correct 8 ms 8184 KB Output is correct
15 Correct 8 ms 8184 KB Output is correct
16 Correct 8 ms 8196 KB Output is correct
17 Correct 8 ms 8184 KB Output is correct
18 Correct 8 ms 8184 KB Output is correct
19 Correct 8 ms 8184 KB Output is correct
20 Correct 8 ms 8180 KB Output is correct
21 Correct 8 ms 8184 KB Output is correct
22 Correct 8 ms 8184 KB Output is correct
23 Correct 8 ms 8184 KB Output is correct
24 Correct 8 ms 8184 KB Output is correct
25 Correct 8 ms 8204 KB Output is correct
26 Correct 8 ms 8184 KB Output is correct
27 Correct 34 ms 9576 KB Output is correct
28 Correct 29 ms 9452 KB Output is correct
29 Correct 35 ms 9576 KB Output is correct
30 Correct 30 ms 9540 KB Output is correct
31 Correct 35 ms 9552 KB Output is correct
32 Correct 29 ms 9480 KB Output is correct
33 Correct 35 ms 9580 KB Output is correct
34 Correct 30 ms 9548 KB Output is correct
35 Correct 65 ms 9676 KB Output is correct
36 Correct 64 ms 9708 KB Output is correct
37 Correct 64 ms 9708 KB Output is correct
38 Correct 64 ms 9836 KB Output is correct
39 Correct 64 ms 9708 KB Output is correct
40 Correct 58 ms 9836 KB Output is correct
41 Correct 59 ms 9712 KB Output is correct
42 Correct 56 ms 9864 KB Output is correct
43 Correct 54 ms 9704 KB Output is correct
44 Correct 58 ms 9708 KB Output is correct
45 Correct 59 ms 9768 KB Output is correct
46 Correct 56 ms 9872 KB Output is correct
47 Correct 55 ms 9704 KB Output is correct
48 Correct 721 ms 22040 KB Output is correct
49 Correct 719 ms 20472 KB Output is correct
50 Correct 718 ms 21580 KB Output is correct
51 Correct 650 ms 24372 KB Output is correct
52 Correct 599 ms 23792 KB Output is correct
53 Correct 644 ms 21896 KB Output is correct
54 Correct 613 ms 20476 KB Output is correct
55 Correct 607 ms 20448 KB Output is correct
56 Correct 589 ms 20748 KB Output is correct
57 Correct 2350 ms 58960 KB Output is correct
58 Correct 2013 ms 53348 KB Output is correct
59 Correct 2011 ms 51788 KB Output is correct
60 Correct 2123 ms 55544 KB Output is correct
61 Correct 2124 ms 52584 KB Output is correct
62 Correct 1254 ms 36224 KB Output is correct
63 Correct 1525 ms 37604 KB Output is correct
64 Correct 1365 ms 36904 KB Output is correct
65 Correct 969 ms 28124 KB Output is correct