Submission #526748

#	Time	Username	Problem	Language	Result	Execution time	Memory
526748		Hydroxic_Acid	Izbori (COCI22_izbori)	C++14	25 / 110	3066 ms	1484 KiB

Main

#include <iostream>
#include <cstring>
#include <map>
using namespace std;
#define ll long long

int n;
ll ways = 0;
int arr[200005];
int total[200005];
int highest = 0;

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> arr[i];
    for(int l = 0; l < n; l++){
        memset(total, 0, sizeof(total));
        total[0] = n;
        highest = 0;
        map<int, int> m;
        for(int r = l; r < n; r++){
            total[m[arr[r]]]--;
            m[arr[r]]++;
            total[m[arr[r]]]++;
            if(highest < m[arr[r]]){
                highest = m[arr[r]];
                if(highest + highest > r - l + 1) ways++;
            }
            else if(total[highest] == 0){
                highest--;
            }
            else if(total[highest] == 1){
                if(highest + highest > r - l + 1) ways++;
            }
        }
    }

    cout << ways;
}

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