oj.uz

Submission #128606

# Submission time Handle Problem Language Result Execution time Memory
128606 2019-07-11T07:21:33 Z 송준혁(#3162) Rope (JOI17_rope) C++14
0 / 100
 54 ms 47864 KB 
#include <bits/stdc++.h>
using namespace std;

int N, M;
int A[1010101];
vector<int> O[1010101], E[1010101];
int cnt[1010101];
int T[4040404];

void init(int id, int s, int e){
    if (s == e){
        T[id] = cnt[s];
        return;
    }
    int mid = (s+e)/2;
    init(id*2, s, mid);
    init(id*2+1, mid+1, e);
}

void update(int id, int s, int e, int t, int v){
    if (e < t || t < s) return;
    if (s == e){
        T[id] += v;
        return;
    }
    int mid = (s+e)/2;
    update(id*2, s, mid, t, v);
    update(id*2+1, mid+1, e, t, v);
    T[id] = max(T[id*2], T[id*2+1]);
}

int RMQ(int id, int s, int e, int ts, int te){
    if (e < ts || te < s) return 0;
    if (ts <= s && e <= te) return T[id];
    int mid = (s+e)/2;
    return max(RMQ(id*2, s, mid, ts, te), RMQ(id*2+1, mid+1, e, ts, te));
}

int main(){
    scanf("%d %d", &N, &M);
    for (int i=1; i<=N; i++){
        scanf("%d", &A[i]);
        cnt[A[i]]++;
    }
    for (int i=1; i<N; i++){
        if (A[i] == A[i+1]) continue;
        if (i & 1){
            E[A[i]].push_back(A[i+1]);
            E[A[i+1]].push_back(A[i]);
        }
        else{
            O[A[i]].push_back(A[i+1]);
            O[A[i+1]].push_back(A[i]);
        }
    }
    init(1, 1, M);
    for (int i=1; i<=M; i++){
        for (int x : O[i]) update(1, 1, M, x, -1);
        int oret = cnt[i] + max(RMQ(1, 1, M, 1, i-1), RMQ(1, 1, M, i+1, M));
        for (int x : O[i]) update(1, 1, M, x, 1);

        for (int x : E[i]) update(1, 1, M, x, -1);
        int eret = cnt[i] + max(RMQ(1, 1, M, 1, i-1), RMQ(1, 1, M, i+1, M));
        for (int x : E[i]) update(1, 1, M, x, 1);
        printf("%d\n", N - max(oret, eret));
    }
    return 0;
}

Compilation message

rope.cpp: In function 'int main()':
rope.cpp:40: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:42: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 45 ms 47864 KB Output is correct
2 Correct 54 ms 47736 KB Output is correct
3 Correct 45 ms 47736 KB Output is correct
4 Correct 46 ms 47736 KB Output is correct
5 Correct 45 ms 47736 KB Output is correct
6 Correct 45 ms 47736 KB Output is correct
7 Incorrect 45 ms 47736 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47864 KB Output is correct
2 Correct 54 ms 47736 KB Output is correct
3 Correct 45 ms 47736 KB Output is correct
4 Correct 46 ms 47736 KB Output is correct
5 Correct 45 ms 47736 KB Output is correct
6 Correct 45 ms 47736 KB Output is correct
7 Incorrect 45 ms 47736 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47864 KB Output is correct
2 Correct 54 ms 47736 KB Output is correct
3 Correct 45 ms 47736 KB Output is correct
4 Correct 46 ms 47736 KB Output is correct
5 Correct 45 ms 47736 KB Output is correct
6 Correct 45 ms 47736 KB Output is correct
7 Incorrect 45 ms 47736 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47864 KB Output is correct
2 Correct 54 ms 47736 KB Output is correct
3 Correct 45 ms 47736 KB Output is correct
4 Correct 46 ms 47736 KB Output is correct
5 Correct 45 ms 47736 KB Output is correct
6 Correct 45 ms 47736 KB Output is correct
7 Incorrect 45 ms 47736 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47864 KB Output is correct
2 Correct 54 ms 47736 KB Output is correct
3 Correct 45 ms 47736 KB Output is correct
4 Correct 46 ms 47736 KB Output is correct
5 Correct 45 ms 47736 KB Output is correct
6 Correct 45 ms 47736 KB Output is correct
7 Incorrect 45 ms 47736 KB Output isn't correct
8 Halted 0 ms 0 KB -