Submission #1164488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164488		pb2008	Izbori (COCI22_izbori)	C++20	40 / 110	3065 ms	3264 KiB

Main

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

#pragma GCC optimize ("03, Ofast, unroll-loops")

const int N = 2e5 + 5, T = 100;
bool mark[N];
long long ans;
int n, a[N], cnt[N], seg[N << 1];

inline void readInput();
inline void compress();
inline void pre();
inline void add(int i);
inline int get(int i);
inline long long calc1(int x);
inline long long calc2(int x);
inline void solve();
inline void writeOutput();

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    readInput();
    solve();
    writeOutput();
    return 0;
}

inline void readInput() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
}

inline void compress() {
    vector<pair<int, int>> v;
    for (int i = 0; i < n; i++)
        v.push_back({a[i], i});
    int tmp = 0;
    sort(v.begin(), v.end());
    for (int i = 0; i < n - 1; i++)
        a[v[i].second] = tmp, tmp += (v[i].first != v[i + 1].first);
    a[v[n - 1].second] = tmp;
}

inline void pre() {
    compress();
    for (int i = 0; i < n; i++)
        cnt[a[i]]++;
}

inline void add(int i) {
    for (; i <= (n << 1 | 1); i += (i & -i))
        seg[i]++;
}

inline int get(int i) {
    int res = 0;
    for (; i; i -= (i & -i))
        res += seg[i];
    return res;
}

inline long long calc1(int x) {
    long long res = 0;
    for (int len = 1; len <= min(2 * cnt[x], n); len++) {
        int num = 0;
        for (int i = 0; i < n; i++) {
            if (i < len)
                num += (a[i] == x);
            else {
                res += ((len / 2) < num);
                num += (a[i] == x) - (a[i - len] == x);
            }
        }
        res += ((len / 2) < num);
    }
    return res;
}

inline long long calc2(int x) {
    int sum = 0;
    long long res = 0;
    memset(seg, 0, sizeof seg);
    for (int i = 0; i < n; i++) {
        sum += 1 - 2 * (a[i] != x);
        res += get(sum + n) + (0 < sum), add(sum + n + 1);
    }
    return res;
}

inline void solve() {
    pre();
    for (int i = 0; i < n; i++) {
        if (mark[a[i]]) continue;
        mark[a[i]] = true;
        if (cnt[a[i]] < T)
            ans += calc1(a[i]);
        else
            ans += calc2(a[i]);
    }
}

inline void writeOutput() {
    cout << ans;
}

Compilation message (stderr)

Main.cpp:4:48: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
    4 | #pragma GCC optimize ("03, Ofast, unroll-loops")
      |                                                ^
Main.cpp:4:48: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
Main.cpp:11:23: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   11 | inline void readInput();
      |                       ^
Main.cpp:11:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:11:23: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:11:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:12:22: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   12 | inline void compress();
      |                      ^
Main.cpp:12:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:12:22: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:12:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:13:17: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   13 | inline void pre();
      |                 ^
Main.cpp:13:17: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:13:17: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:13:17: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:14:22: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   14 | inline void add(int i);
      |                      ^
Main.cpp:14:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:14:22: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:14:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:15:21: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   15 | inline int get(int i);
      |                     ^
Main.cpp:15:21: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:15:21: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:15:21: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:16:29: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   16 | inline long long calc1(int x);
      |                             ^
Main.cpp:16:29: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:16:29: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:16:29: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:17:29: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   17 | inline long long calc2(int x);
      |                             ^
Main.cpp:17:29: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:17:29: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:17:29: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:18:19: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   18 | inline void solve();
      |                   ^
Main.cpp:18:19: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:18:19: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:18:19: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:19:25: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   19 | inline void writeOutput();
      |                         ^
Main.cpp:19:25: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:19:25: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
Main.cpp:19:25: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:21:10: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   21 | int main() {
      |          ^
Main.cpp:21:10: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:29:23: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   29 | inline void readInput() {
      |                       ^
Main.cpp:29:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:35:22: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   35 | inline void compress() {
      |                      ^
Main.cpp:35:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:46:17: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   46 | inline void pre() {
      |                 ^
Main.cpp:46:17: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:52:22: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   52 | inline void add(int i) {
      |                      ^
Main.cpp:52:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:57:21: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   57 | inline int get(int i) {
      |                     ^
Main.cpp:57:21: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:64:29: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   64 | inline long long calc1(int x) {
      |                             ^
Main.cpp:64:29: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:81:29: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   81 | inline long long calc2(int x) {
      |                             ^
Main.cpp:81:29: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:92:19: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
   92 | inline void solve() {
      |                   ^
Main.cpp:92:19: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
Main.cpp:104:25: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
  104 | inline void writeOutput() {
      |                         ^
Main.cpp:104:25: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]

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