Submission #1180842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180842		jerzyk	Rope (JOI17_rope)	C++20	100 / 100	423 ms	105324 KiB

rope

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1000'007;
int tab[N], answer[N];

pair<int, int> pos[N];
vector<int> wh[N], con[N];
int bst1, bst2;

void Do(int n, int m, int s)
{
    bst1 = 0; bst2 = 0;
    for(int i = s; i <= n - 1; i += 2)
    {
        ++pos[tab[i]].st; ++pos[tab[i + 1]].st;
        con[tab[i]].pb(tab[i + 1]);
        if(tab[i] != tab[i + 1])
            con[tab[i + 1]].pb(tab[i]);
    }
    for(int i = 1; i <= m; ++i)
        wh[pos[i].st].pb(i);
    for(int i = n; i >= 1; --i)
        for(int j = 0; j < (int)wh[i].size(); ++j)
        {
            if(bst1 == 0) bst1 = wh[i][j];
            else if(bst2 == 0) bst2 = wh[i][j];
            pos[wh[i][j]].nd = j;
        }
}

void C(int v, int r)
{
    int l = wh[pos[v].st].back();
    swap(wh[pos[v].st].back(), wh[pos[v].st][pos[v].nd]);
    swap(pos[v].nd, pos[l].nd);
    wh[pos[v].st].pop_back();

    pos[v].st += r;
    wh[pos[v].st].pb(v);
    pos[v].nd = (int)wh[pos[v].st].size() - 1;
    if(pos[bst1].st < pos[bst2].st) swap(bst1, bst2);
    if(r > 0)
    {
        if(pos[v].st > pos[bst1].st)
        {
            bst2 = bst1;
            bst1 = v;
        }else if(v != bst1 && pos[v].st > pos[bst2].st)
            bst2 = v;
        return;
    }

    if(bst2 != v) return;
    l = pos[v].st;
    if(bst2 == v && ((int)wh[l + 1].size() >= 2 || wh[l + 1][0] != bst1))
    {
        bst2 = wh[l + 1][0];
        if(bst2 == bst1) bst2 = wh[l + 1][1];
    }
}

void Solve()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
        answer[i] = n;

    for(int i = 1; i <= n; ++i)
        cin >> tab[i];
    for(int s = 1; s <= 2; ++s)
    {
        for(int i = 0; i <= n; ++i)
        {
            pos[i] = make_pair(0, 0);
            wh[i].clear(); con[i].clear();
        }
        Do(n, m, s);
        if(s == 2)
            C(tab[1], 1);
        if(s % 2 == n % 2)
            C(tab[n], 1);

        //cout << "A: " << s << "\n";
        for(int i = 1; i <= m; ++i)
        {
            int sum = pos[i].st;
            for(int j = 0; j < (int)con[i].size(); ++j)
                if(con[i][j] != i)
                    C(con[i][j], -1);
            int a = pos[bst1].st;
            if(bst1 == i) a = pos[bst2].st;

            //cout << sum << " " << a << " | " << bst1 << " " << bst2 << "\n";

            answer[i] = min(answer[i], n - (a + sum));
            for(int j = 0; j < (int)con[i].size(); ++j)
                if(con[i][j] != i)
                    C(con[i][j], 1);
        }
    }
    for(int i = 1; i <= m; ++i)
        cout << answer[i] << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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