Submission #703988

#	Time	Username	Problem	Language	Result	Execution time	Memory
703988		willychan	Izbori (COCI22_izbori)	C++14	40 / 110	3056 ms	5428 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
int n;

struct BIT{
	vector<int> arr;
	void init(){
		arr.resize(n+2,0);
		fill(arr.begin(),arr.end(),0);
	}
	void modify(int ind){
		while(ind<=n+1){
			arr[ind]+=1;
			ind+=(ind&-ind);
		}
	}
	int query(int ind){
		int r = 0;
		while(ind){
			r+=arr[ind];
			ind-=(ind&-ind);
		}
		return r;
	}
} bit;

ll get(vector<int> &p){
	vector<int> d;
	for(auto i : p) d.push_back(i);
	sort(d.begin(),d.end());
	d.resize(unique(d.begin(),d.end())-d.begin());
	for(int i=0;i<=n;i++)	p[i] = lower_bound(d.begin(),d.end(),p[i])-d.begin()+1;
	bit.init();	
	ll ans = 0;
	for(int i=0;i<=n;i++){
		ans+=bit.query(p[i]-1);			
		bit.modify(p[i]);
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	bit.init();
	int arr[n];
	vector<int> d;
	for(int i=0;i<n;i++){
		cin>>arr[i];	
		d.push_back(arr[i]);
	}
	sort(d.begin(),d.end());										
	d.resize(unique(d.begin(),d.end())-d.begin());
	vector<int> allcnt(d.size(),0);
	for(int i=0;i<n;i++){
		arr[i] = lower_bound(d.begin(),d.end(),arr[i])-d.begin();
		allcnt[arr[i]]++;
	}
	int B = 2*sqrt(n);
	int C = (B/2)-1;
	ll ans = 0;
	for(int i=0;i<n;i++){
		int maxn = 0;
		int maxstuff = -1;
		vector<int> cnt(d.size(),0);
		for(int j=i;j<i+B && j<n ;j++){
			cnt[arr[j]]++;
			if(maxn<cnt[arr[j]]){
				maxn = cnt[arr[j]];
				maxstuff = arr[j];
			}
			if(2*maxn>(j-i+1) && allcnt[maxstuff]<C) ans++;
		}
	}
	for(int s=0;s<d.size();s++){
		if(allcnt[s]<C) continue;
		vector<int> p(n+1);					
		int a = 0;
		int b = 0;
		p[0]=0;
		for(int i=1;i<=n;i++){
			if(arr[i-1]==s) a++;
			b++;
			p[i] = 2*a-b;
		}
		ll g = get(p);
		ans+=g;
	}
	cout<<ans<<"\n";
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:78:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int s=0;s<d.size();s++){
      |              ~^~~~~~~~~

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