oj.uz

Submission #696678

# Submission time Handle Problem Language Result Execution time Memory
696678 2023-02-07T03:33:10 Z minhnhatnoe Izbori (COCI22_izbori) C++14
110 / 110
 1571 ms 4332 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


const int SQRT = 450;
inline void cprs(vector<int> &a){
    vector<int> b = a;
    sort(b.begin(), b.end());
    for (int &x: a)
        x = lower_bound(b.begin(), b.end(), x) - b.begin();
}
vector<int> a, cnt;
vector<int> ccnt;
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n;
    a.resize(n);
    for (int i=0; i<n; i++)
        cin >> a[i];
    cprs(a);
    cnt.resize(n);
    for (int i=0; i<n; i++)
        cnt[a[i]]++;
    ccnt.resize(n);

    ll result = 0;
    // Numbers <= SQRT
    for (int start=0; start<n; start++){
        pair<int, int> pval(-1, -1);
        int max_step = min(SQRT*2, n - start + 1);
        for (int step=1; step < max_step; step++){
            int need = step/2 + 1;
            int val = a[start+step-1];
            ccnt[val]++;
            pval = max(pval, make_pair(ccnt[val], val));
            if (pval.first >= need && cnt[pval.second] <= SQRT)
                result++;
        }
        for (int step=1; step < max_step; step++){
            int val = a[start+step-1];
            ccnt[val]--;
        }
    }
    // Numbers > SQRT
    ccnt.resize(n*2+1);
    ccnt[n] = 1;
    for (int val=0; val<n; val++){
        if (cnt[val] <= SQRT) continue;
        int prefix = 0;
        int pos = n;
        for (int i=0; i<n; i++){
            if (a[i] == val){
                prefix += ccnt[pos];
                pos++;
            }
            else{
                pos--;
                prefix -= ccnt[pos];
            }
            result += prefix;
            ccnt[pos]++;
        }
        pos = n;
        for (int i=0; i<n; i++){
            if (a[i] == val) pos++;
            else pos--;
            ccnt[pos]--;
        }
    }
    cout << result << "\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 10 ms 340 KB Output is correct
10 Correct 10 ms 344 KB Output is correct
11 Correct 10 ms 340 KB Output is correct
12 Correct 10 ms 340 KB Output is correct
13 Correct 10 ms 340 KB Output is correct
14 Correct 10 ms 340 KB Output is correct
15 Correct 10 ms 340 KB Output is correct
16 Correct 10 ms 348 KB Output is correct
17 Correct 9 ms 340 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1051 ms 2896 KB Output is correct
2 Correct 1360 ms 3628 KB Output is correct
3 Correct 793 ms 2280 KB Output is correct
4 Correct 1430 ms 3844 KB Output is correct
5 Correct 1478 ms 3936 KB Output is correct
6 Correct 1561 ms 4200 KB Output is correct
7 Correct 1561 ms 4204 KB Output is correct
8 Correct 1563 ms 4204 KB Output is correct
9 Correct 1571 ms 4204 KB Output is correct
10 Correct 1570 ms 4284 KB Output is correct
11 Correct 1053 ms 4204 KB Output is correct

Subtask #4
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 10 ms 340 KB Output is correct
10 Correct 10 ms 344 KB Output is correct
11 Correct 10 ms 340 KB Output is correct
12 Correct 10 ms 340 KB Output is correct
13 Correct 10 ms 340 KB Output is correct
14 Correct 10 ms 340 KB Output is correct
15 Correct 10 ms 340 KB Output is correct
16 Correct 10 ms 348 KB Output is correct
17 Correct 9 ms 340 KB Output is correct
18 Correct 1051 ms 2896 KB Output is correct
19 Correct 1360 ms 3628 KB Output is correct
20 Correct 793 ms 2280 KB Output is correct
21 Correct 1430 ms 3844 KB Output is correct
22 Correct 1478 ms 3936 KB Output is correct
23 Correct 1561 ms 4200 KB Output is correct
24 Correct 1561 ms 4204 KB Output is correct
25 Correct 1563 ms 4204 KB Output is correct
26 Correct 1571 ms 4204 KB Output is correct
27 Correct 1570 ms 4284 KB Output is correct
28 Correct 1053 ms 4204 KB Output is correct
29 Correct 1067 ms 4196 KB Output is correct
30 Correct 203 ms 1084 KB Output is correct
31 Correct 426 ms 1724 KB Output is correct
32 Correct 1109 ms 3944 KB Output is correct
33 Correct 456 ms 1996 KB Output is correct
34 Correct 483 ms 2068 KB Output is correct
35 Correct 296 ms 1356 KB Output is correct
36 Correct 178 ms 840 KB Output is correct
37 Correct 215 ms 1044 KB Output is correct
38 Correct 1359 ms 4192 KB Output is correct
39 Correct 1357 ms 4200 KB Output is correct
40 Correct 1367 ms 4204 KB Output is correct
41 Correct 1355 ms 4200 KB Output is correct
42 Correct 1381 ms 4196 KB Output is correct
43 Correct 1223 ms 4196 KB Output is correct
44 Correct 1224 ms 4228 KB Output is correct
45 Correct 1253 ms 4200 KB Output is correct
46 Correct 1267 ms 4204 KB Output is correct
47 Correct 1273 ms 4200 KB Output is correct
48 Correct 1303 ms 4200 KB Output is correct
49 Correct 1250 ms 4328 KB Output is correct
50 Correct 1138 ms 4212 KB Output is correct
51 Correct 1141 ms 4200 KB Output is correct
52 Correct 1201 ms 4236 KB Output is correct
53 Correct 1196 ms 4232 KB Output is correct
54 Correct 1121 ms 4332 KB Output is correct