Submission #526814

#	Time	Username	Problem	Language	Result	Execution time	Memory
526814		joelau	Izbori (COCI22_izbori)	C++14	25 / 110	3023 ms	12420 KiB

Main

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

long long N,A[200005], freq[400005];
vector<long long> A1, lst[200005];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N;
    for (long long i = 0; i < N; ++i) {
        cin >> A[i];
        A1.push_back(A[i]);
    }
    sort(A1.begin(),A1.end());
    A1.resize(unique(A1.begin(),A1.end())-A1.begin());
    for (long long i = 0; i < N; ++i) {
        A[i] = lower_bound(A1.begin(),A1.end(),A[i]) - A1.begin();
        lst[A[i]].push_back(i);
    }
    long long ans = 0;
    for (long long n = 0; n < N; ++n) {
        long long cnt = N, last = 0;
        memset(freq,0,sizeof(freq));
        freq[cnt]++;
        for (long long i = 0, j = 0; i < N; ++i) {
            if (j < lst[n].size() && i == lst[n][j]) last += freq[cnt++], j++;
            else last -= freq[--cnt];
            ans += last, freq[cnt]++;
        }
    }
    cout << ans;

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:26:19: 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]
   26 |             if (j < lst[n].size() && i == lst[n][j]) last += freq[cnt++], j++;
      |                 ~~^~~~~~~~~~~~~~~

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