Submission #1180043

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180043		Szymon_Pilipczuk	Rope (JOI17_rope)	C++20	0 / 100	0 ms	328 KiB

rope

#include <bits/stdc++.h>
using namespace std;
int tr[2000000];
int n,m;
void add(int p,int v)
{
    p+=m;
    tr[p]+=v;
    p/=2;
    while(p > 0)
    {
        tr[p] = max(tr[p*2],tr[p*2+1]);
        p/=2;
    }
}
int check()
{
    return tr[1];
}
int main()
{
    cin>>n>>m;
    int c[n];
    unordered_map<int,int> mm;
    unordered_map<int,vector<int>> p1;
    unordered_map<int,vector<int>> p2;
    for(int i =0 ;i<n;i++)
    {
        cin>>c[i];
        c[i]--;
        mm[c[i]]++;
        /*if(i%2 == 0 && i > 0)
        {
            if(c[i-1] != c[i])
            {
                p2[c[i]].push_back(c[i-1]);
            }
        }
        else if(i%2 == 1)
        {
            if(c[i-1] != c[i])
            {
                p1[c[i]].push_back(c[i-1]);
            }
        }*/
        add(c[i],1);
    }
    for(int i = 0;i<n;i++)
    {
        if(i > 0)
        {
            if(c[i-1] != c[i])
            {
                if(i%2 == 0)
                {
                    p2[c[i]].push_back(c[i-1]);
                }
                else
                {
                    p1[c[i]].push_back(c[i-1]);
                }
            }
        }
        if(i < n-1)
        {
            if(c[i+1] != c[i])
            {
                if(i%2 == 0)
                {
                    p1[c[i]].push_back(c[i+1]);
                }
                else
                {
                    p2[c[i]].push_back(c[i+1]);
                }
            }
        }
    }
    for(int i = 0;i<m;i++)
    {
        int ans;
        for(int j = 0;j<p1[i].size();j++)
        {
            add(p1[i][j],-1);
        }
        add(i,-1e9);
        ans = n-check()-mm[i];
        for(int j = 0;j<p1[i].size();j++)
        {
            add(p1[i][j],1);
        }
        for(int j = 0;j<p2[i].size();j++)
        {
            add(p2[i][j],-1);
        }
        //cout<<mm[i]<<" "<<check()<<"\n";
        ans = min(ans,n-check()-mm[i]);
        for(int j = 0;j<p2[i].size();j++)
        {
            add(p2[i][j],1);
        }
        add(i,1e9);
        cout<<ans<<"\n";

    }
}

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