oj.uz

Submission #534589

# Submission time Handle Problem Language Result Execution time Memory
534589 2022-03-08T11:01:08 Z N1NT3NDO Izbori (COCI22_izbori) C++14
110 / 110
 2831 ms 5560 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) (int)x.size()
#define fi first
#define sd second
#define all(x) x.begin(), x.end()
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = (int)2e5 + 50;
const int MX = 450;
int n, a[N], cnt[N], f[2 * N], mk[N], skok[N];
vector<int> vec;
bool was[N];
ll ans;

void upd(int x)
{
    for(int i = x; i < 2 * N; i = i | (i + 1)) f[i]++;
}

int get(int x)
{
    int res = 0;

    for(int i = x; i >= 0; i = (i & (i + 1)) - 1)
      res += f[i];
    return res;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("input.txt", "r", stdin);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        vec.pb(a[i]);
    }

    sort(all(vec));

    vec.resize(unique(all(vec)) - vec.begin());

    int m = sz(vec);

    for(int i = 1; i <= n; i++)
    {
        a[i] = lower_bound(all(vec), a[i]) - vec.begin();
        cnt[a[i]]++;
    }

    for(int i = 0; i < m; i++)
    {

        if (cnt[i] < MX) continue;

        for(int j = 0; j < 2 * N; j++) f[j] = 0;

        was[i] = 1;

        upd(N);

        int pr = 0;

        for(int j = 1; j <= n; j++)
        {
            if (a[j] == i) pr++;
            else pr--;
            ans += (ll)get(N + pr - 1);
            upd(N + pr);
        }
    }



    int id = 1;
    for(int i = 1; i <= n; i++)
    {
        int mx = 0, who = -1;

        for(int j = i; j <= min(n, i + MX + MX); j++)
        {
            if (mk[a[j]] != id)
            {
                mk[a[j]] = id;
                skok[a[j]] = 0;
            }

            skok[a[j]]++;

            if (skok[a[j]] > mx)
            {
                mx = skok[a[j]];
                who = a[j];
            }

            if (!was[who] && mx > (j - i + 1) / 2)
              ans++;
        }

        id++;
    }



    cout << ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 3396 KB Output is correct
2 Correct 708 ms 3656 KB Output is correct
3 Correct 412 ms 3020 KB Output is correct
4 Correct 740 ms 3792 KB Output is correct
5 Correct 781 ms 3768 KB Output is correct
6 Correct 823 ms 3912 KB Output is correct
7 Correct 832 ms 3924 KB Output is correct
8 Correct 822 ms 3904 KB Output is correct
9 Correct 828 ms 3980 KB Output is correct
10 Correct 832 ms 3904 KB Output is correct
11 Correct 580 ms 3912 KB Output is correct

Subtask #4
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 7 ms 332 KB Output is correct
10 Correct 8 ms 340 KB Output is correct
11 Correct 8 ms 340 KB Output is correct
12 Correct 7 ms 364 KB Output is correct
13 Correct 7 ms 336 KB Output is correct
14 Correct 7 ms 332 KB Output is correct
15 Correct 7 ms 332 KB Output is correct
16 Correct 7 ms 332 KB Output is correct
17 Correct 6 ms 1868 KB Output is correct
18 Correct 556 ms 3396 KB Output is correct
19 Correct 708 ms 3656 KB Output is correct
20 Correct 412 ms 3020 KB Output is correct
21 Correct 740 ms 3792 KB Output is correct
22 Correct 781 ms 3768 KB Output is correct
23 Correct 823 ms 3912 KB Output is correct
24 Correct 832 ms 3924 KB Output is correct
25 Correct 822 ms 3904 KB Output is correct
26 Correct 828 ms 3980 KB Output is correct
27 Correct 832 ms 3904 KB Output is correct
28 Correct 580 ms 3912 KB Output is correct
29 Correct 575 ms 5440 KB Output is correct
30 Correct 137 ms 1348 KB Output is correct
31 Correct 277 ms 2240 KB Output is correct
32 Correct 723 ms 4500 KB Output is correct
33 Correct 301 ms 2372 KB Output is correct
34 Correct 326 ms 2488 KB Output is correct
35 Correct 203 ms 1744 KB Output is correct
36 Correct 117 ms 1232 KB Output is correct
37 Correct 147 ms 1360 KB Output is correct
38 Correct 897 ms 3988 KB Output is correct
39 Correct 911 ms 3912 KB Output is correct
40 Correct 938 ms 3936 KB Output is correct
41 Correct 919 ms 3984 KB Output is correct
42 Correct 905 ms 3972 KB Output is correct
43 Correct 852 ms 5436 KB Output is correct
44 Correct 877 ms 5444 KB Output is correct
45 Correct 880 ms 5560 KB Output is correct
46 Correct 865 ms 5528 KB Output is correct
47 Correct 866 ms 5480 KB Output is correct
48 Correct 2067 ms 4276 KB Output is correct
49 Correct 2076 ms 4268 KB Output is correct
50 Correct 1185 ms 4160 KB Output is correct
51 Correct 1180 ms 4140 KB Output is correct
52 Correct 2831 ms 4416 KB Output is correct
53 Correct 2616 ms 4312 KB Output is correct
54 Correct 1769 ms 4260 KB Output is correct