Submission #537648

#	Time	Username	Problem	Language	Result	Execution time	Memory
537648		qwerasdfzxcl	Rope (JOI17_rope)	C++14	100 / 100	1332 ms	136976 KiB

rope

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int a[1001000], cnt[1001000];
struct Seg{
    int tree[2002000], sz;
    void init(int n){
        sz = n;
        for (int i=sz;i<sz*2;i++) tree[i] = cnt[i-sz];
        for (int i=sz-1;i;i--) tree[i] = max(tree[i<<1], tree[i<<1|1]);
    }
    void update(int p, int x){
        for (tree[p+=sz]+=x;p>1;p>>=1) tree[p>>1] = max(tree[p], tree[p^1]);
    }
}tree;
vector<int> E[1001000], O[1001000];

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i=1;i<=n;i++){
        scanf("%d", a+i);
        cnt[a[i]]++;
    }
    tree.init(m+1);

    for (int i=1;i<=n;i+=2){
        if (i+1<=n && a[i]!=a[i+1]){
            O[a[i]].push_back(a[i+1]);
            O[a[i+1]].push_back(a[i]);
        }
    }

    for (int i=2;i<=n;i+=2){
        if (i+1<=n && a[i]!=a[i+1]){
            E[a[i]].push_back(a[i+1]);
            E[a[i+1]].push_back(a[i]);
        }
    }

    for (int i=1;i<=m;i++){
        int ans = 1e9;
        tree.update(i, -cnt[i]);

        for (auto &x:O[i]) tree.update(x, -1);
        ans = min(ans, (int)O[i].size() + n - (cnt[i] + (int)O[i].size() + tree.tree[1]));
        for (auto &x: O[i]) tree.update(x, 1);
        //printf("%d ", ans);

        for (auto &x:E[i]) tree.update(x, -1);
        ans = min(ans, (int)E[i].size() + n - (cnt[i] + (int)E[i].size() + tree.tree[1]));
        for (auto &x: E[i]) tree.update(x, 1);

        tree.update(i, cnt[i]);
        printf("%d\n", ans);
    }
    return 0;
}

Compilation message (stderr)

rope.cpp: In function 'int main()':
rope.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
rope.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%d", a+i);
      |         ~~~~~^~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 20 / 20