Submission #474648

#	Time	Username	Problem	Language	Result	Execution time	Memory
474648		MilosMilutinovic	Diversity (CEOI21_diversity)	C++14	4 / 100	7036 ms	2380 KiB

diversity

#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 (stderr)

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 / 4
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 16
• Subtask 5: 0 / 26
• Subtask 6: 0 / 36