oj.uz

Submission #205669

# Submission time Handle Problem Language Result Execution time Memory
205669 2020-02-29T12:10:05 Z Kastanda Rope (JOI17_rope) C++11
0 / 100
 35 ms 47356 KB 
// 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 & 1) * 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

rope.cpp: In function 'int main()':
rope.cpp:25:38: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
             int nxt = i + 1 - (i ^ j & 1) * 2;
                                    ~~^~~
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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47356 KB Output is correct
2 Correct 35 ms 47352 KB Output is correct
3 Incorrect 33 ms 47352 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47356 KB Output is correct
2 Correct 35 ms 47352 KB Output is correct
3 Incorrect 33 ms 47352 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47356 KB Output is correct
2 Correct 35 ms 47352 KB Output is correct
3 Incorrect 33 ms 47352 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47356 KB Output is correct
2 Correct 35 ms 47352 KB Output is correct
3 Incorrect 33 ms 47352 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47356 KB Output is correct
2 Correct 35 ms 47352 KB Output is correct
3 Incorrect 33 ms 47352 KB Output isn't correct
4 Halted 0 ms 0 KB -