Submission #299462

#	Time	Username	Problem	Language	Result	Execution time	Memory
299462		XmtosX	Rope (JOI17_rope)	C++17	100 / 100	1771 ms	78072 KiB

rope

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,a[N],cnt[N],ans[N],cnt1[N],here[N],maxx;
bool yes;
vector <int> v[N],V;
set<pair<int,int> > s;
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        cnt[a[i]]++;
        cnt1[a[i]]++;
        ans[a[i]]=n-cnt[i];
        maxx=max(maxx,cnt[a[i]]);
    }
    for (int i=1;i<=m;i++)
        here[cnt[i]]++;
    for (int o=0;o<2;o++)
    {
        for (int i=1;i<=m;i++)
            v[i].clear();
        if ((n-o)%2)
            yes=true;
        else
            yes=false;
        for (int i=o;i+1<n;i+=2)
        {
            v[a[i]].push_back(i);
            if (a[i]!=a[i+1])
                v[a[i+1]].push_back(i);
        }
        for (int i=1;i<=m;i++)
        {
            V.clear();
            int tot=n;
            if (o&&a[0]==i)
            {
                if (here[cnt1[i]]==1&&cnt1[i]==maxx)
                    maxx--;
                here[cnt1[i]]--;
                cnt1[i]--;
                here[cnt1[i]]++;
                V.push_back(i);
                tot--;
            }
            for (int j=0;j<v[i].size();j++)
            {
                int idx= v[i][j];
                V.push_back(a[idx]);
                if (here[cnt1[a[idx]]]==1&&cnt1[a[idx]]==maxx)
                    maxx--;
                here[cnt1[a[idx]]]--;
                cnt1[a[idx]]--;
                here[cnt1[a[idx]]]++;
                tot-=(a[idx]==i);
                idx++;
                V.push_back(a[idx]);
                if (here[cnt1[a[idx]]]==1&&cnt1[a[idx]]==maxx)
                    maxx--;
                here[cnt1[a[idx]]]--;
                cnt1[a[idx]]--;
                here[cnt1[a[idx]]]++;
                tot-=(a[idx]==i);
            }
            if (yes&&a[n-1]==i)
            {
                if (here[cnt1[i]]==1&&cnt1[i]==maxx)
                    maxx--;
                here[cnt1[i]]--;
                cnt1[i]--;
                here[cnt1[i]]++;
                V.push_back(i);
                tot--;
            }
            ans[i]=min(ans[i],tot-maxx);
            for (int j=0;j<V.size();j++)
            {
                here[cnt1[V[j]]]--;
                here[cnt[V[j]]]++;
                cnt1[V[j]]=cnt[V[j]];
                maxx=max(maxx,cnt[V[j]]);
            }
        }
    }
    for (int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}
/*
5 3
1 2 3 3 2

7 3
1 2 2 1 3 3 3

10 3
2 2 1 1 3 3 2 1 1 2

*/

Compilation message (stderr)

rope.cpp: In function 'int main()':
rope.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             for (int j=0;j<v[i].size();j++)
      |                          ~^~~~~~~~~~~~
rope.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             for (int j=0;j<V.size();j++)
      |                          ~^~~~~~~~~
rope.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   10 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
rope.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~

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