oj.uz

Submission #1114525

# Submission time Handle Problem Language Result Execution time Memory
1114525 2024-11-19T07:02:55 Z vjudge1 Diversity (CEOI21_diversity) C++17
14 / 100
 7000 ms 2640 KB 
//Dost SEFEROĞLU
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e18;
const int N = 2e5+50,Q = 2e5+50;
 
void solve() { 
    int n,q;
    cin >> n >> q;
    vi a(n+1);
    for (int i=1;i<=n;i++) cin >> a[i];
    while (q--) {
        int L,R;
        cin >> L >> R;
        n = R-L+1;
        map<int,int> mp;
        for (int j = L;j<=R;j++) mp[a[j]]++;
        vi ps;
        for (auto it : mp) ps.push_back(it.ss);
        int k = ps.size();
        vi perm;
        for (int i = 0;i<k;i++) perm.push_back(i);
        int ans = inf;
        do {
            int anss = 0;
            int cur = 1;
            for (int i = 0;i<k;i++) {
                int it = ps[perm[i]];
                int r = cur+it-1;
                anss+=n*(n+1)/2-cur*(cur-1)/2-(n-r)*(n-r+1)/2;
                cur = r+1;
            }
            if (anss < ans) ans = anss;
        }while (next_permutation(perm.begin(),perm.end()));
        cout << ans << '\n';
    }
}                    
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 8 ms 620 KB Output is correct
9 Correct 78 ms 336 KB Output is correct
10 Correct 934 ms 444 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 14 ms 1104 KB Output is correct
5 Correct 88 ms 1944 KB Output is correct
6 Correct 941 ms 2640 KB Output is correct
7 Correct 945 ms 2640 KB Output is correct
8 Correct 947 ms 2640 KB Output is correct
9 Correct 943 ms 2640 KB Output is correct
10 Correct 950 ms 2640 KB Output is correct
11 Correct 944 ms 2640 KB Output is correct
12 Correct 940 ms 2640 KB Output is correct
13 Correct 967 ms 2640 KB Output is correct
14 Correct 933 ms 2640 KB Output is correct
15 Correct 958 ms 2640 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 14 ms 1104 KB Output is correct
5 Correct 88 ms 1944 KB Output is correct
6 Correct 941 ms 2640 KB Output is correct
7 Correct 945 ms 2640 KB Output is correct
8 Correct 947 ms 2640 KB Output is correct
9 Correct 943 ms 2640 KB Output is correct
10 Correct 950 ms 2640 KB Output is correct
11 Correct 944 ms 2640 KB Output is correct
12 Correct 940 ms 2640 KB Output is correct
13 Correct 967 ms 2640 KB Output is correct
14 Correct 933 ms 2640 KB Output is correct
15 Correct 958 ms 2640 KB Output is correct
16 Execution timed out 7052 ms 336 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 14 ms 1104 KB Output is correct
5 Correct 88 ms 1944 KB Output is correct
6 Correct 941 ms 2640 KB Output is correct
7 Correct 945 ms 2640 KB Output is correct
8 Correct 947 ms 2640 KB Output is correct
9 Correct 943 ms 2640 KB Output is correct
10 Correct 950 ms 2640 KB Output is correct
11 Correct 944 ms 2640 KB Output is correct
12 Correct 940 ms 2640 KB Output is correct
13 Correct 967 ms 2640 KB Output is correct
14 Correct 933 ms 2640 KB Output is correct
15 Correct 958 ms 2640 KB Output is correct
16 Execution timed out 7052 ms 336 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 8 ms 620 KB Output is correct
9 Correct 78 ms 336 KB Output is correct
10 Correct 934 ms 444 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 2 ms 508 KB Output is correct
14 Correct 14 ms 1104 KB Output is correct
15 Correct 88 ms 1944 KB Output is correct
16 Correct 941 ms 2640 KB Output is correct
17 Correct 945 ms 2640 KB Output is correct
18 Correct 947 ms 2640 KB Output is correct
19 Correct 943 ms 2640 KB Output is correct
20 Correct 950 ms 2640 KB Output is correct
21 Correct 944 ms 2640 KB Output is correct
22 Correct 940 ms 2640 KB Output is correct
23 Correct 967 ms 2640 KB Output is correct
24 Correct 933 ms 2640 KB Output is correct
25 Correct 958 ms 2640 KB Output is correct
26 Execution timed out 7052 ms 336 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #6
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 8 ms 620 KB Output is correct
9 Correct 78 ms 336 KB Output is correct
10 Correct 934 ms 444 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 2 ms 508 KB Output is correct
14 Correct 14 ms 1104 KB Output is correct
15 Correct 88 ms 1944 KB Output is correct
16 Correct 941 ms 2640 KB Output is correct
17 Correct 945 ms 2640 KB Output is correct
18 Correct 947 ms 2640 KB Output is correct
19 Correct 943 ms 2640 KB Output is correct
20 Correct 950 ms 2640 KB Output is correct
21 Correct 944 ms 2640 KB Output is correct
22 Correct 940 ms 2640 KB Output is correct
23 Correct 967 ms 2640 KB Output is correct
24 Correct 933 ms 2640 KB Output is correct
25 Correct 958 ms 2640 KB Output is correct
26 Execution timed out 7052 ms 336 KB Time limit exceeded
27 Halted 0 ms 0 KB -