oj.uz

Submission #533493

# Submission time Handle Problem Language Result Execution time Memory
533493 2022-03-06T07:47:18 Z Slavita Izbori (COCI22_izbori) C++14
25 / 110
 89 ms 1612 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define ve vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi pair<int,int>
#define all(v) v.begin(),v.end()
#define si(v) (int)v.size()
#define en '\n'
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_muiltiset tree<int, null_type,less_equal<>, rb_tree_tag,tree_order_statistics_node_update>
//#define int long long
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;

const int N = 2e5 + 228;
const int big = 1e9 + 228;
const ll llbig = 1e18 + 228;
//ordered_set os; // os.order_of_key(4), (*os.find_by_order(5))
int n, m, ans, a[N], pr[N];
map<int, int> mem;

int get(int l, int r){
    return pr[r] - pr[l - 1];
}

//#undef int
int main(){
    //#define int long long
    iostream::sync_with_stdio(false); cin.tie(0); ios_base::sync_with_stdio(false); cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        pr[i] = pr[i - 1] + (a[i] == 1);
    }

    if (n > 2007){
        for (int i = 1; i <= n; i++){
            int l = 1, r = i;
            while(l < r){
                int md = (l + r + 1) / 2;
                if (a[i] == 1){
                    if (get(md, i) > (i - md + 1) / 2) r = md - 1; else l = md;
                }

                if (a[i] == 2){
                    if (get(md, i) < (i - md + 1) / 2) r = md - 1; else l = md;
                }
            }
            ans += i - l + 1;
        }
        cout << ans;
        return 0;
    }

    for (int i = 1; i <= n; i++){
        int cur = a[i], an = 0;
        mem.clear();
        for (int j = i; j <= n; j++){
            mem[a[j]]++;
            if (mem[a[j]] > mem[cur]) cur = a[j];
            if (mem[cur] > (j - i + 1) / 2) an++;
        }
        ans += an;
    }
    cout << ans;
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 2 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 85 ms 368 KB Output is correct
8 Correct 2 ms 324 KB Output is correct
9 Correct 82 ms 340 KB Output is correct
10 Correct 87 ms 340 KB Output is correct
11 Correct 89 ms 340 KB Output is correct
12 Correct 79 ms 336 KB Output is correct
13 Correct 74 ms 352 KB Output is correct
14 Correct 78 ms 340 KB Output is correct
15 Correct 88 ms 332 KB Output is correct
16 Correct 81 ms 332 KB Output is correct
17 Correct 12 ms 332 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 1612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 2 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 85 ms 368 KB Output is correct
8 Correct 2 ms 324 KB Output is correct
9 Correct 82 ms 340 KB Output is correct
10 Correct 87 ms 340 KB Output is correct
11 Correct 89 ms 340 KB Output is correct
12 Correct 79 ms 336 KB Output is correct
13 Correct 74 ms 352 KB Output is correct
14 Correct 78 ms 340 KB Output is correct
15 Correct 88 ms 332 KB Output is correct
16 Correct 81 ms 332 KB Output is correct
17 Correct 12 ms 332 KB Output is correct
18 Incorrect 17 ms 1612 KB Output isn't correct
19 Halted 0 ms 0 KB -