oj.uz

Submission #26764

# Submission time Handle Problem Language Result Execution time Memory
26764 2017-07-05T12:16:53 Z RayaBurong25_1 medians (balkan11_medians) C++14
100 / 100
 49 ms 3068 KB 
#include <stdio.h>
int B[100005];
int Used[200005];
int Fen[200005];
int min, max;
int N;
int Query(int pos)
{
    int sum = 0;
    for (; pos > 0; pos -= pos&-pos)
        sum += Fen[pos];
    return sum;
}
void Update(int pos)
{
    Used[pos] = 1;
    for (; pos <= 2*N - 1; pos += pos&-pos)
        Fen[pos]++;
}
int main()
{
    scanf("%d", &N);
    min = 1;
    max = 2*N - 1;
    int i, r, cnt;
    for (i = 0; i < N; i++)
        scanf("%d", &B[i]);
    for (i = 0; i < N; i++)
    {
        // printf("i%d ", i);
        cnt = 0;
        if (!Used[B[i]])
        {
            Used[B[i]] = 1;
            Update(B[i]);
            printf("%d ", B[i]);
            cnt++;
        }
        r = Query(B[i]);
        // printf("//%d//", r);
        if (i == 0)
            continue;
        if (cnt == 1)
        {
            if (r < i + 1)
            {
                while (Used[min])
                    min++;
                Used[min] = 1;
                Update(min);
                printf("%d ", min);
            }
            else
            {
                while (Used[max])
                    max--;
                Used[max] = 1;
                Update(max);
                printf("%d ", max);
            }
        }
        else
        {
            if (r == i - 1)
            {
                while (Used[min])
                    min++;
                Used[min] = 1;
                Update(min);
                printf("%d ", min);
                while (Used[min])
                    min++;
                Used[min] = 1;
                Update(min);
                printf("%d ", min);
            }
            else if (r == i)
            {
                while (Used[min])
                    min++;
                Used[min] = 1;
                Update(min);
                printf("%d ", min);
                while (Used[max])
                    max--;
                Used[max] = 1;
                Update(max);
                printf("%d ", max);
            }
            else
            {
                while (Used[max])
                    max--;
                Used[max] = 1;
                Update(max);
                printf("%d ", max);
                while (Used[max])
                    max--;
                Used[max] = 1;
                Update(max);
                printf("%d ", max);
            }
        }
    }
}

Compilation message

medians.cpp: In function 'int main()':
medians.cpp:22:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
                    ^
medians.cpp:27:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &B[i]);
                           ^

Subtask #1
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3068 KB Output is correct
2 Correct 0 ms 3068 KB Output is correct
3 Correct 0 ms 3068 KB Output is correct
4 Correct 0 ms 3068 KB Output is correct
5 Correct 0 ms 3068 KB Output is correct
6 Correct 0 ms 3068 KB Output is correct
7 Correct 0 ms 3068 KB Output is correct
8 Correct 0 ms 3068 KB Output is correct
9 Correct 0 ms 3068 KB Output is correct
10 Correct 0 ms 3068 KB Output is correct
11 Correct 0 ms 3068 KB Output is correct
12 Correct 0 ms 3068 KB Output is correct
13 Correct 0 ms 3068 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3068 KB Output is correct
2 Correct 0 ms 3068 KB Output is correct
3 Correct 3 ms 3068 KB Output is correct
4 Correct 3 ms 3068 KB Output is correct
5 Correct 13 ms 3068 KB Output is correct
6 Correct 23 ms 3068 KB Output is correct
7 Correct 49 ms 3068 KB Output is correct