oj.uz

Submission #534590

# Submission time Handle Problem Language Result Execution time Memory
534590 2022-03-08T11:03:06 Z N1NT3NDO Izbori (COCI22_izbori) C++14
40 / 110
 3000 ms 3704 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;
}

Compilation message

Main.cpp:11: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   11 | #pragma GCC optimization ("O3")
      | 
Main.cpp:12: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   12 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 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 1 ms 332 KB Output is correct
2 Correct 0 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 332 KB Output is correct
9 Correct 8 ms 332 KB Output is correct
10 Correct 8 ms 368 KB Output is correct
11 Correct 7 ms 332 KB Output is correct
12 Correct 7 ms 368 KB Output is correct
13 Correct 7 ms 372 KB Output is correct
14 Correct 7 ms 372 KB Output is correct
15 Correct 6 ms 368 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 561 ms 3016 KB Output is correct
2 Correct 758 ms 3400 KB Output is correct
3 Correct 448 ms 2764 KB Output is correct
4 Correct 812 ms 3400 KB Output is correct
5 Correct 835 ms 3400 KB Output is correct
6 Correct 903 ms 3528 KB Output is correct
7 Correct 876 ms 3528 KB Output is correct
8 Correct 878 ms 3576 KB Output is correct
9 Correct 891 ms 3704 KB Output is correct
10 Correct 853 ms 3528 KB Output is correct
11 Correct 581 ms 3528 KB Output is correct

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 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 332 KB Output is correct
9 Correct 8 ms 332 KB Output is correct
10 Correct 8 ms 368 KB Output is correct
11 Correct 7 ms 332 KB Output is correct
12 Correct 7 ms 368 KB Output is correct
13 Correct 7 ms 372 KB Output is correct
14 Correct 7 ms 372 KB Output is correct
15 Correct 6 ms 368 KB Output is correct
16 Correct 7 ms 332 KB Output is correct
17 Correct 6 ms 1868 KB Output is correct
18 Correct 561 ms 3016 KB Output is correct
19 Correct 758 ms 3400 KB Output is correct
20 Correct 448 ms 2764 KB Output is correct
21 Correct 812 ms 3400 KB Output is correct
22 Correct 835 ms 3400 KB Output is correct
23 Correct 903 ms 3528 KB Output is correct
24 Correct 876 ms 3528 KB Output is correct
25 Correct 878 ms 3576 KB Output is correct
26 Correct 891 ms 3704 KB Output is correct
27 Correct 853 ms 3528 KB Output is correct
28 Correct 581 ms 3528 KB Output is correct
29 Correct 629 ms 3520 KB Output is correct
30 Correct 146 ms 1104 KB Output is correct
31 Correct 293 ms 1740 KB Output is correct
32 Correct 735 ms 3388 KB Output is correct
33 Correct 310 ms 1984 KB Output is correct
34 Correct 314 ms 1860 KB Output is correct
35 Correct 228 ms 1360 KB Output is correct
36 Correct 123 ms 1020 KB Output is correct
37 Correct 157 ms 1104 KB Output is correct
38 Correct 960 ms 3588 KB Output is correct
39 Correct 934 ms 3596 KB Output is correct
40 Correct 953 ms 3648 KB Output is correct
41 Correct 938 ms 3580 KB Output is correct
42 Correct 928 ms 3528 KB Output is correct
43 Correct 877 ms 3592 KB Output is correct
44 Correct 880 ms 3476 KB Output is correct
45 Correct 876 ms 3572 KB Output is correct
46 Correct 883 ms 3520 KB Output is correct
47 Correct 934 ms 3588 KB Output is correct
48 Correct 2055 ms 3584 KB Output is correct
49 Correct 2020 ms 3588 KB Output is correct
50 Correct 1239 ms 3648 KB Output is correct
51 Correct 1242 ms 3692 KB Output is correct
52 Execution timed out 3003 ms 3600 KB Time limit exceeded
53 Halted 0 ms 0 KB -