Submission #1261977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261977		shidou26	Izbori (COCI22_izbori)	C++20	110 / 110	604 ms	19196 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define endl '\n'
#define fi first
#define se second
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define filter(v) v.resize(unique(all(v)) - v.begin())
#define dbg(x) "[" #x << " = " << x << "]"

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> bool maximize(T &a, T b) {
    if(a < b) return a = b, true;
    else return false;
}

template<typename T> bool minimize(T &a, T b) {
    if(a > b) return a = b, true;
    else return false;
}

template<typename T1, typename T2> T2 rnd(T1 l, T2 r) {
    return uniform_int_distribution<T2>(l, r)(rng);
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, int> pli;
typedef pair<long long, long long> pll;

const int N = 4e5 + 3;
const int S = 500;

int n;
int a[N];

int cnt[N];
ll answer = 0;
vector<int> cps;
vector<int> color[N];

void process() {
    sort(all(cps)); filter(cps);
    for(int i = 1; i <= n; i++) {
        a[i] = lower_bound(all(cps), a[i]) - cps.begin() + 1;
        color[a[i]].push_back(i);
    }

    for(int c = 1; c <= n; c++) {
        if(sz(color[c]) >= S) {
            int prefix = n, total = 0;
            fill(cnt, cnt + 1 + 2 * n, 0);

            cnt[prefix]++;
            for(int i = 1; i <= n; i++) {
                int value = (a[i] == c ? 1 : -1);
                prefix += value;

                if(value == 1) total += cnt[prefix - 1];
                else total -= cnt[prefix];

                cnt[prefix]++;
                answer += total;
            }
        }
    }

    fill(cnt, cnt + 1 + n, 0);
    for(int i = 1; i <= n; i++) {
        int bound = min(n, i + 2 * S - 1), dominate = 0;

        for(int j = i; j <= bound; j++) {
            if(sz(color[a[j]]) < S) {
                cnt[a[j]]++;
                maximize(dominate, cnt[a[j]]);

                if(dominate >= (j - i + 1) / 2 + 1) answer++;
            }
        }

        for(int j = i; j <= bound; j++) cnt[a[j]] = 0;
    }

    cout << answer << endl;
}

void input() {
    cin >> n;

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        cps.push_back(a[i]);
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #define task "VBAUCU"
    if(fopen(task".INP", "r")) {
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    int testcase = 1; // cin >> testcase;
    for(int i = 1; i <= testcase; i++) {
        input();
        process();
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 70 / 70