Submission #205670

#	Time	Username	Problem	Language	Result	Execution time	Memory
205670		Kastanda	Rope (JOI17_rope)	C++11	100 / 100	1523 ms	139492 KiB

rope

// In The Name Of The Queen
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 1000006;
int n, m, A[N], C[N], S[N * 2];
vector < int > V[N][2];
inline void Add(int i, int val)
{
    S[i += m - 1] += val;
    for (; i; i >>= 1)
        S[i >> 1] = max(S[i], S[i ^ 1]);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++)
        scanf("%d", &A[i]);
    for (int i = 1; i <= n; i ++)
    {
        C[A[i]] ++;
        for (int j = 0; j <= 1; j ++)
        {
            int nxt = i + 1 - ((i + j) % 2) * 2;
            if (A[nxt] && A[nxt] != A[i])
                V[A[i]][j].push_back(A[nxt]);
        }
        Add(A[i], 1);
    }
    for (int c = 1; c <= m; c ++)
    {
        int Mn = n - C[c];
        Add(c, -C[c]);
        for (int j = 0; j <= 1; j ++)
        {
            for (int a : V[c][j])
                Add(a, -1);
            Mn = min(Mn, n - C[c] - S[1]);
            for (int a : V[c][j])
                Add(a, 1);
        }
        Add(c, C[c]);
        printf("%d\n", Mn);
    }
    return 0;
}

Compilation message (stderr)

rope.cpp: In function 'int main()':
rope.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     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]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~

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