Submission #730612

#	Time	Username	Problem	Language	Result	Execution time	Memory
730612		vjudge1	Izbori (COCI22_izbori)	C++17	110 / 110	2268 ms	17996 KiB

Main

#include <iostream>
#include <map>
#include <vector>
using namespace std;
map<long long int, int> m;
long long int a[200005], c[200005];
vector<int> g[200005];
struct FENWICK {
    vector<long long int> v;
    FENWICK (int n) {
        v.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            v[i] = 0;
        }
    }
    long long int build(long long int x) {
        long long int res = 0;
        x++;
        while (x) {
            res += v[x];
            x -= (x & (-x));
        }
        return res;
    }
    void update(long long int x, long long int y) {
        x++;
        while (x < v.size()) {
            v[x] += y;
            x += (x & (-x));
        }
    }
    long long int sum(long long int l, long long int r) {
        if (l == 0) return build(r);
        return build(r) - build(l - 1);
    }
};
int main() {
    long long int n, d = 0, res = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (!m.count(a[i])) {
            m[a[i]] = m.size();
        }
        a[i] = m[a[i]];
        g[a[i]].push_back(i);
    }
    for (long long int x = 0; x <= n; x++) {
        if (g[x].empty()) continue;
        if (g[x].size() >= 450) {
            c[0] = 0;
            for (int i = 1; i <= n; i++) {
                c[i] = c[i - 1];
                if (a[i - 1] == x) c[i]++;
            }
            FENWICK f(n + c[n] * 2 + 1);
            for (int j = 0; j < n; j++) {
                f.update(c[j] * 2 + n - j + 2, 1);
                res += f.sum(0, c[j + 1] * 2 + n - j);
            }
        }
        else {
            vector<int> v = g[x];
            for (int i = 0; i < v.size(); i++) {
                for (int j = i; j < v.size(); j++) {
                    long long int l, r;
                    if (i == 0) l = v[i];
                    else l = v[i] - v[i - 1] - 1;
                    if (j == v.size() - 1) r = n - v[j];
                    else r = v[j + 1] - v[j];
                    long long int k = (j - i) * 2 + v[i] - v[j] + 1;
                    res += max(min(l, k) - max(k - r, 0ll) + 1, 0ll) * k;
                    long long int ll = max(k - r, 0ll), rr = min(l, k);
                    if (ll <= rr) {
                        res -= (rr + 1) * rr / 2 - ll * (ll - 1) / 2;
                    }
                    res += r * max(min(k - r - 1, l) + 1, 0ll);
                }
            }
        }
    }
    cout << res;
}

Compilation message (stderr)

Main.cpp: In member function 'void FENWICK::update(long long int, long long int)':
Main.cpp:27:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         while (x < v.size()) {
      |                ~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:64:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             for (int i = 0; i < v.size(); i++) {
      |                             ~~^~~~~~~~~~
Main.cpp:65:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |                 for (int j = i; j < v.size(); j++) {
      |                                 ~~^~~~~~~~~~
Main.cpp:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |                     if (j == v.size() - 1) r = n - v[j];
      |                         ~~^~~~~~~~~~~~~~~
Main.cpp:38:22: warning: unused variable 'd' [-Wunused-variable]
   38 |     long long int n, d = 0, res = 0;
      |                      ^

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