oj.uz

Submission #533582

# Submission time Handle Problem Language Result Execution time Memory
533582 2022-03-06T10:48:38 Z topovik Izbori (COCI22_izbori) C++14
40 / 110
 3000 ms 31664 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second

using namespace std;

typedef long long ll;
typedef long double ld;

const ll oo = 1e18 + 7;

const ll N = 5e5 + 10;
const ll N1 = 5e6;
const ll M = 2e3 + 10;

vector <ll> ps[N];
ll b[N];
map <ll, ll> mp;
ll ans = 0;

int val[N];
int key[N];

int t;

int main()
{
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin >> n;
    ll a[n];
    vector <ll> cmp;
    for (ll i = 0; i < n; i++) cin >> a[i], cmp.pb(a[i]);
    sort(cmp.begin(), cmp.end());
    cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
    for (ll i = 0; i < n; i++) a[i] = lower_bound(cmp.begin(), cmp.end(), a[i]) - cmp.begin();
    for (ll i = 0; i < n; i++) ps[a[i]].pb(i);
    for (ll i = 0; i < n; i++)
    {
        t++;
        int nom_mx = N - 1;
        for (int j = i; j < min(n, i + M); j++)
        {
            if (key[a[j]] != t)
            {
                key[a[j]] = t;
                val[a[j]] = 0;
            }
            val[a[j]]++;
            if (val[a[j]] > val[nom_mx]) nom_mx = a[j];
            if (val[nom_mx] * 2 > (j - i + 1))
            {
                if (ps[nom_mx].size() <= M / 2) ans++;
            }
        }
    }
    for (ll i = 0; i < n; i++)
        if (ps[i].size() > M / 2)
    {
        for (ll j = 0; j < n; j++) b[j] = 0;
        for (auto j : ps[i]) b[j] = 1;
        mp.clear();
        ll sum1 = 0;
        ll kol = 0;
        for (ll j = 0; j < n; j++)
        {
            sum1 += b[j];
            mp[sum1 * 2 - (j + 1)]++;
            if (sum1 * 2 - (j + 1) > 0) kol++;
        }
        ans += kol;
        ll c = 1;
        sum1 = 0;
        for (ll j = 0; j < n; j++)
        {
            sum1 += b[j];
            mp[sum1 * 2 - (j + 1)]--;
            if (sum1 * 2 - (j + 1) >= c) kol--;

            if (b[j] == 0)
            {
                c--;
                kol += mp[c];
            }
            else
            {
                kol -= mp[c];
                c++;
            }
            ans += kol;
        }
        cout << endl;
    }
    cout << ans;
}
/*
5 3
2 1 1 2 2 3
2 3 3 4 4 5
4 1 1 2 2 3 3 4 4 5
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 7 ms 11980 KB Output is correct
3 Correct 6 ms 12044 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 6 ms 11980 KB Output is correct
6 Correct 6 ms 12000 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 7 ms 11980 KB Output is correct
3 Correct 6 ms 12044 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 6 ms 11980 KB Output is correct
6 Correct 6 ms 12000 KB Output is correct
7 Correct 7 ms 12108 KB Output is correct
8 Correct 6 ms 11980 KB Output is correct
9 Correct 12 ms 12148 KB Output is correct
10 Correct 13 ms 12148 KB Output is correct
11 Correct 12 ms 12152 KB Output is correct
12 Correct 12 ms 12152 KB Output is correct
13 Correct 12 ms 12148 KB Output is correct
14 Correct 12 ms 12108 KB Output is correct
15 Correct 12 ms 12120 KB Output is correct
16 Correct 13 ms 12112 KB Output is correct
17 Correct 14 ms 12272 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 962 ms 17428 KB Output is correct
2 Correct 1203 ms 18876 KB Output is correct
3 Correct 727 ms 16080 KB Output is correct
4 Correct 1350 ms 18972 KB Output is correct
5 Correct 1335 ms 18904 KB Output is correct
6 Correct 1401 ms 19692 KB Output is correct
7 Correct 1411 ms 19764 KB Output is correct
8 Correct 1403 ms 19772 KB Output is correct
9 Correct 1400 ms 19268 KB Output is correct
10 Correct 1413 ms 19276 KB Output is correct
11 Correct 1397 ms 30852 KB Output is correct

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 7 ms 11980 KB Output is correct
3 Correct 6 ms 12044 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 6 ms 11980 KB Output is correct
6 Correct 6 ms 12000 KB Output is correct
7 Correct 7 ms 12108 KB Output is correct
8 Correct 6 ms 11980 KB Output is correct
9 Correct 12 ms 12148 KB Output is correct
10 Correct 13 ms 12148 KB Output is correct
11 Correct 12 ms 12152 KB Output is correct
12 Correct 12 ms 12152 KB Output is correct
13 Correct 12 ms 12148 KB Output is correct
14 Correct 12 ms 12108 KB Output is correct
15 Correct 12 ms 12120 KB Output is correct
16 Correct 13 ms 12112 KB Output is correct
17 Correct 14 ms 12272 KB Output is correct
18 Correct 962 ms 17428 KB Output is correct
19 Correct 1203 ms 18876 KB Output is correct
20 Correct 727 ms 16080 KB Output is correct
21 Correct 1350 ms 18972 KB Output is correct
22 Correct 1335 ms 18904 KB Output is correct
23 Correct 1401 ms 19692 KB Output is correct
24 Correct 1411 ms 19764 KB Output is correct
25 Correct 1403 ms 19772 KB Output is correct
26 Correct 1400 ms 19268 KB Output is correct
27 Correct 1413 ms 19276 KB Output is correct
28 Correct 1397 ms 30852 KB Output is correct
29 Correct 1361 ms 30804 KB Output is correct
30 Correct 287 ms 14028 KB Output is correct
31 Correct 609 ms 15836 KB Output is correct
32 Correct 1455 ms 20144 KB Output is correct
33 Correct 624 ms 16072 KB Output is correct
34 Correct 658 ms 16192 KB Output is correct
35 Correct 416 ms 14916 KB Output is correct
36 Correct 247 ms 13888 KB Output is correct
37 Correct 303 ms 14148 KB Output is correct
38 Correct 1513 ms 26224 KB Output is correct
39 Correct 1505 ms 26392 KB Output is correct
40 Correct 1504 ms 26212 KB Output is correct
41 Correct 1506 ms 26444 KB Output is correct
42 Correct 1481 ms 26388 KB Output is correct
43 Correct 1911 ms 29356 KB Output is correct
44 Correct 1936 ms 29552 KB Output is correct
45 Correct 1935 ms 29336 KB Output is correct
46 Correct 1957 ms 29440 KB Output is correct
47 Correct 1936 ms 29364 KB Output is correct
48 Correct 1378 ms 31028 KB Output is correct
49 Correct 1377 ms 31288 KB Output is correct
50 Execution timed out 3056 ms 31664 KB Time limit exceeded
51 Halted 0 ms 0 KB -