Submission #711490

#	Time	Username	Problem	Language	Result	Execution time	Memory
711490		devvops	Izbori (COCI22_izbori)	C++14	0 / 110	1887 ms	4432 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
using namespace std;
#define pb push_back
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end() 
#define speed ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
const int mod = (int) 1e9 + 7;
const int N = (int) 2e5 + 100, bruh = 500;

ll a[N], tree[N], n, k;
map<int, int> cnt;

void upd(int idx){
	for(int i = idx; i < N; i += i & -i){
		tree[i] += 1;
	}
}

ll get(int x){
	ll ans = 0;
	for (int i = x; i > 0; i -= i & -i) {
         ans += tree[i];
    }
    return ans;
}

signed main(){
   	speed;
   	cin >> n >> k;
   	for(int i = 1; i <= n; i++){
   		cin >> a[i];
   		cnt[a[i]]++;
   	} 
   	ll ans = 0;
   	for(auto i : cnt){
   		if(i.S > bruh){
   			memset(tree, 0, sizeof(tree));
	   		vector<int> v;
	   		for(int j = 1; j <= n; j++){
	   			if(a[j] == i.F) v.pb(1);
	   			else v.pb(-1);
	   		}
	   		int s = 0;
	   		upd(n + 1);
	   		for(int j = 0; j < n; j++){
	   			s += v[j];
	   			if(s < 0){
	   				upd(abs(s));
	   				ans += get(n) - get(abs(s));
	   			}
	   			else{
	   				upd(s + (n + 1));
	   				ans += get(n) - get(0);
	   				ans += get(n + s) - get(n);
	   			}
	   		}
   		}
   	}
   	for(int i = 1; i <= n; i++){
   		map<int, int> cnt1;
   		int lst = -1, lstA = -1;
   		for(int j = i; j <= n; j++){
   			if((j - i + 1) > 2 * bruh) break;
   			if(a[j] == lstA) lst++;
   			++cnt1[a[j]];
   			int sz = (j - i) + 1;
   			if(lst > (sz / 2) && cnt[lstA] <= bruh) ans++;
   			else if(cnt1[a[j]] > (sz / 2) && cnt[a[j]] <= bruh){
   				ans++;
   				lst = cnt1[a[j]];
   				lstA = a[j];
   			}
   		}
   	}
   	cout << ans;
}

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