oj.uz

Submission #474648

# Submission time Handle Problem Language Result Execution time Memory
474648 2021-09-19T09:00:55 Z MilosMilutinovic Diversity (CEOI21_diversity) C++14
4 / 100
 7000 ms 2380 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 500;

int A[N], n, q, cnt[N], B[N];
int ans[N];

int main(){
        scanf("%d%d", &n, &q);
        for(int i = 1;i <= n;i++){
                scanf("%d", A + i);
                cnt[A[i]]++;
        }
        for(int i = 1;i <= q;i++){
                int l, r; scanf("%d%d", &l, &r);
        }
        iota(B, B + N, 0);
        sort(B, B + N, [&](int i, int j){
                return cnt[i] < cnt[j];
        });
        int l = 1, r = n;
        for(int i = 1;i <= N;i++){
                for(int j = 1;j <= cnt[B[i]];j++){
                        if(i & 1) ans[l++] = B[i];
                        else ans[r--] = B[i];
                }
        }
        long long sum = 0;
        for(int i = 1;i <= n;i++){
                map < int, int > bio;
                int diff = 0;
                for(int j = i;j <= n;j++){
                        if(!bio[ans[j]]) diff++;
                        bio[ans[j]]++;
                        sum += diff;
                }
        }
        printf("%lld", sum);
        return 0;
}

Compilation message

diversity.cpp: In function 'int main()':
diversity.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         scanf("%d%d", &n, &q);
      |         ~~~~~^~~~~~~~~~~~~~~~
diversity.cpp:13:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |                 scanf("%d", A + i);
      |                 ~~~~~^~~~~~~~~~~~~
diversity.cpp:17:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 int l, r; scanf("%d%d", &l, &r);
      |                           ~~~~~^~~~~~~~~~~~~~~~
diversity.cpp:25:43: warning: iteration 300499 invokes undefined behavior [-Waggressive-loop-optimizations]
   25 |                 for(int j = 1;j <= cnt[B[i]];j++){
      |                                        ~~~^
diversity.cpp:24:25: note: within this loop
   24 |         for(int i = 1;i <= N;i++){
      |                       ~~^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1484 KB Output is correct
2 Correct 7 ms 1484 KB Output is correct
3 Correct 7 ms 1484 KB Output is correct
4 Correct 7 ms 1484 KB Output is correct
5 Correct 7 ms 1484 KB Output is correct
6 Correct 7 ms 1484 KB Output is correct
7 Correct 7 ms 1484 KB Output is correct
8 Correct 7 ms 1484 KB Output is correct
9 Correct 7 ms 1484 KB Output is correct
10 Correct 7 ms 1420 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1484 KB Output is correct
2 Correct 10 ms 1492 KB Output is correct
3 Correct 306 ms 1560 KB Output is correct
4 Execution timed out 7036 ms 2380 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1484 KB Output is correct
2 Correct 10 ms 1492 KB Output is correct
3 Correct 306 ms 1560 KB Output is correct
4 Execution timed out 7036 ms 2380 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1484 KB Output is correct
2 Correct 10 ms 1492 KB Output is correct
3 Correct 306 ms 1560 KB Output is correct
4 Execution timed out 7036 ms 2380 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1484 KB Output is correct
2 Correct 7 ms 1484 KB Output is correct
3 Correct 7 ms 1484 KB Output is correct
4 Correct 7 ms 1484 KB Output is correct
5 Correct 7 ms 1484 KB Output is correct
6 Correct 7 ms 1484 KB Output is correct
7 Correct 7 ms 1484 KB Output is correct
8 Correct 7 ms 1484 KB Output is correct
9 Correct 7 ms 1484 KB Output is correct
10 Correct 7 ms 1420 KB Output is correct
11 Correct 8 ms 1484 KB Output is correct
12 Correct 10 ms 1492 KB Output is correct
13 Correct 306 ms 1560 KB Output is correct
14 Execution timed out 7036 ms 2380 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1484 KB Output is correct
2 Correct 7 ms 1484 KB Output is correct
3 Correct 7 ms 1484 KB Output is correct
4 Correct 7 ms 1484 KB Output is correct
5 Correct 7 ms 1484 KB Output is correct
6 Correct 7 ms 1484 KB Output is correct
7 Correct 7 ms 1484 KB Output is correct
8 Correct 7 ms 1484 KB Output is correct
9 Correct 7 ms 1484 KB Output is correct
10 Correct 7 ms 1420 KB Output is correct
11 Correct 8 ms 1484 KB Output is correct
12 Correct 10 ms 1492 KB Output is correct
13 Correct 306 ms 1560 KB Output is correct
14 Execution timed out 7036 ms 2380 KB Time limit exceeded
15 Halted 0 ms 0 KB -