Submission #851461

#	Time	Username	Problem	Language	Result	Execution time	Memory
851461		epicci23	Izbori (COCI22_izbori)	C++17	110 / 110	2447 ms	12092 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

const int N = 4e5 + 5;

int fw[N];

void upd(int c){
	for(;c<N;c+=c&-c) fw[c]++;
}

int query(int c,int res=0){
	for(;c;c-=c&-c) res+=fw[c];
	return res;
}

void solve(){
	int n;
	cin >> n;

	int ar[n+1];
	for(int i=1;i<=n;i++){
		cin >> ar[i];
	}

    int ans=0;

    vector<int> zip;

    for(int i=1;i<=n;i++) zip.pb(ar[i]);

    sort(all(zip));
    zip.erase(unique(all(zip)),zip.end()); // dont forget std::unique function!

    for(int i=1;i<=n;i++) ar[i]=upper_bound(all(zip),ar[i])-zip.begin();
    
    const int BL = 500;
    
    int freq[n+1];
    memset(freq,0,sizeof(freq));

    for(int i=1;i<=n;i++) freq[ar[i]]++;
     
    for(int i=1;i<=n;i++){
       if(freq[i]<BL) continue;
       int nar[n+1];
       for(int j=1;j<=n;j++){
       	 if(ar[j]==i) nar[j]=1;
       	 else nar[j]=-1;
       }
       memset(fw,0,sizeof(fw));
       int cur=0;
       upd(cur+n);
       for(int j=1;j<=n;j++){
         cur+=nar[j];
         ans+=query(cur+n-1);
         upd(cur+n);
       }
    }
 
    for(int i=1;i<=2*BL;i++){
     if(i>n) continue;
   	 int cfreq[n+1];
   	 pair<int,int> coco={-1,-1};
   	 memset(cfreq,0,sizeof(cfreq));
   	 for(int j=1;j<=n;j++){
       cfreq[ar[j]]++;
       if(j>i) cfreq[ar[j-i]]--;
       if(cfreq[ar[j]]>i/2) coco={ar[j],cfreq[ar[j]]};
       if(coco.first!=-1 && cfreq[coco.first]<=i/2) coco={-1,-1};
       if(j>=i && coco.first!=-1 && freq[coco.first]<BL) ans++;
   	 }
   }

   cout << ans << endl;
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();

  return 0;
}

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