Submission #299457

#	Time	Username	Problem	Language	Result	Execution time	Memory
299457		XmtosX	Rope (JOI17_rope)	C++17	80 / 100	2559 ms	124408 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];
bool yes;
vector <int> v[N],V;
set<long long > s;
long long mul (long long x,int y)
{
    x*=10000000ll;
    x+=y;
    return x;
}
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];
    }
    for (int i=1;i<=m;i++)
        s.insert(mul(cnt[i],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)
            {
                cnt1[i]--;
                V.push_back(i);
                tot--;
            }
            for (int j=0;j<v[i].size();j++)
            {
                int idx= v[i][j];
                if (cnt1[a[idx]]==cnt[a[idx]])
                    V.push_back(a[idx]);
                cnt1[a[idx]]--;
                tot-=(a[idx]==i);
                idx++;
                if (cnt1[a[idx]]==cnt[a[idx]])
                    V.push_back(a[idx]);
                cnt1[a[idx]]--;
                tot-=(a[idx]==i);
            }
            if (yes&&a[n-1]==i)
            {
                cnt1[i]--;
                if (cnt[i]==cnt1[i])
                    V.push_back(i);
                tot--;
            }
            for (int j=0;j<V.size();j++)
            {
                s.erase(mul(cnt[V[j]],V[j]));
                s.insert(mul(cnt1[V[j]],V[j]));
            }
            long long p = *s.rbegin();
            p/=10000000ll;
            ans[i]=min(ans[i],(int)(tot-p));
            for (int j=0;j<V.size();j++)
            {
                s.erase(mul(cnt1[V[j]],V[j]));
                s.insert(mul(cnt[V[j]],V[j]));
                cnt1[V[j]]=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:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             for (int j=0;j<v[i].size();j++)
      |                          ~^~~~~~~~~~~~
rope.cpp:70:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             for (int j=0;j<V.size();j++)
      |                          ~^~~~~~~~~
rope.cpp:78:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             for (int j=0;j<V.size();j++)
      |                          ~^~~~~~~~~
rope.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
rope.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~

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