Submission #1011244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011244		0pt1mus23	Izbori (COCI22_izbori)	C++14	110 / 110	1832 ms	55888 KiB

Main

/*
    not my sol, edu
*/
#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define endl '\n'
#define drop(x) cout<<(x)<<endl; return;
#define all(x) x.begin(),x.end()

const int mod = 1e9 +7, sze = 2e5+10, inf = LLONG_MAX, prime = 1453;
int arr[sze];
int brr[sze];

int dac(int l,int r){
    if(l==r){
        return 1;
    }
    if(l>r){
        return 0;
    }
    int ans=0;
    int mid = (l+r)/2;
    set<int> cand;
    map<int,int> cnt;

    for(int i = mid-1;i>=l;i--){
        ++cnt[arr[i]];
        if(cnt[arr[i]]> (mid-i)/2){
            cand.ins(arr[i]);
        }
    }
    cnt.clear();
    for(int i = mid;i<=r;i++){
        ++cnt[arr[i]];
        if(cnt[arr[i]]>(i-mid+1)/2){
            cand.ins(arr[i]);
        }
    }
    for(auto v:cand){
        for(int i=l;i<=r;i++){
            if(arr[i]==v){
                brr[i]=+1;
            }
            else{
                brr[i]=-1;
            }
        }
        cnt.clear();
        int sum=0;
        ++cnt[0];
        for(int i=l;i<mid;i++){
            sum+=brr[i];
            ++cnt[sum];
        }
        int upto = (r-l+1);
        for(int i = -upto;i<=upto;i++){
            cnt[i]+=cnt[i-1];
        }
        for(int i = mid;i<=r;i++){
            sum+=brr[i];
            ans+=cnt[sum-1];
        }


    }
    // cout<<l<<" "<<r<<" "<<ans<<endl;
    return ans + dac(l,mid-1) + dac(mid+1,r);
}

void mal(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    cout<<dac(1,n)<<endl;
} 
 
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    clock_t z = clock();
    int tt = 1;
    // cin>>tt;
    
    while(tt--){
        mal();        
    }
    
    // cerr<<(double)(clock() - z) / CLOCKS_PER_SEC <<endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:86:13: warning: unused variable 'z' [-Wunused-variable]
   86 |     clock_t z = clock();
      |             ^

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