Submission #1266415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266415		namhh	Izbori (COCI22_izbori)	C++20	110 / 110	190 ms	15404 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e5+5;
const int base = 2e5;
const int bl = 450;
int n,a[N],b[N],cnt[2*N];
map<int,int>mp;
vector<int>adj[N];
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        mp[a[i]]++;
    }
    int tot = 0; 
    for(auto it: mp) mp[it.fi] = ++tot;
    for(int i = 1; i <= n; i++){
        a[i] = mp[a[i]];
        adj[a[i]].push_back(i);
    }
    long long ans = 0;
    for(int i = 1; i <= tot; i++){
        if(adj[i].size() <= bl){
            for(int j = 0; j < adj[i].size(); j++){
                for(int k = j; k < adj[i].size(); k++){
                    int sum = k-j+1;
                    int len = adj[i][k]-adj[i][j]+1;
                    if(2*sum > len){
                        int rem = 2*sum-len-1;
                        int l;
                        if(j > 0) l = adj[i][j]-adj[i][j-1]-1;
                        else l = adj[i][j]-1;
                        l = min(rem,l);
                        int r;
                        if(k+1 < adj[i].size()) r= adj[i][k+1]-adj[i][k]-1;
                        else r = n-adj[i][k];
                        r = min(rem,r);
                        int l1 = 0;
                        int r1 = min(rem-r-1,l);
                        if(l1 <= r1) ans += (r1-l1+1)*(r+1);
                        int l2 = max(0,rem-r);
                        int r2 = min(l,rem);
                        if(l2 <= r2) ans += ((rem+1)*(r2-l2+1)-(l2+r2)*(r2-l2+1)/2);
                    }
                }
            }
        }
        else{
        	for(int j = 1; j <= n; j++){
        		if(a[j] == i) b[j] = 1;
        		else b[j] = -1;
			}
			memset(cnt,0,sizeof(cnt));
			int x = base;
			int cur = 0;
			cnt[base]++;
			for(int j = 1; j <= n; j++){
				x += b[j];
				if(b[j] == 1) cur += cnt[x-1];
				else cur -= cnt[x];
				ans += cur;
				cnt[x]++;
			}
		}
    }
    cout << ans;
}

//-----+--+----+-==-=*==--=+----------==----------------+=-----==-=+-==----------------
//---===+=----+=----=*=+=*+----------==-----------+=-----==-----==--+-+----------------
//---+=**=-=+---------***+----=------=-------------=-------+-----==-+--=---------------
//----*+-+++**++------=#+----===-----=-------------=-------==-----+-=+=-+--------------
//----++#***+*+++-----=+-----=-=----+---------------+-------+=-----*=-==-+-------------
//---+=+**++**++++==++*=-----===----+---------------+----=---=-----=*+*=-==------------
//---++**==+--++++++***-----+-+-----+---------------==---==--==-----+**---+------------
//----++*#=-+++***+***------+-+-----+----------------=----+---*+=---=*#=-=-+-----------
//-----=**+++*+++**%++-----=--+-----+----------------=----*=--==+==++***-=+==----------
//-------**#**++*%%@==-----=--+-----+-------------=+++++=-+=---+=+=-=+**--+++----------
//---------====+@@%@-=-----+--+--=+++++--------------=----+==--===---+*---+==+---------
//-----------=@*%%%%-=-----+=-==-----=---------------=----+--=-==+-=-=*----++==--------
//----------%#=%=#%%==-----=+--=-----=---------------+----+--===*=*==**=---+-++--------
//--------+@++@=*@%*-=-----=+=-=-----==-------------++-*%%%***=++-+=-+-+---=-===-------
//-------#%-=%=+@%@+-=-----=+=--+++*==*=------------**@*##%*--=-+-----=+---==-+==------
//------=%+-=%=%*@@--=-----=*#*=+*###@%*---------=+*++%***##=-+-+------+---==-=+=------
//-------%*-=%@+@@+-*=-----+-=--@##*##=+==----------=-#*#***-==-+------+---==--++------
//-------+@=+@@*@*-=-=-----=-==-*#%*##=----------------++=+=----+------+---==--==+-----
//--------%@@%%@*=--+=-----=---+=+#==*-------------------==-----+------+---==---=+-----
//----------%+=#-=--==-----+-------===--------------------------*------+---==---+==----
//---------##-%+-=---=-----++----------------------------------=*------=---==---=+=----
//--------=#-*@=-=---=-----**=----------------=----------------+*------=---==----++----
//-------=@==%*-==---=-----++*---------------------------------*+------+---==----++=---
//------=%*-=@--==---=-----+++*-------------------------------**=------+---==----==+---
//------*#--##--==---=-----+++*+--------------------+--------+**=------+---=-----==+---
//-----=@=--@*---=---=-----+++#+*=--------=+=----=+=-------=#+**-------+---+-----==+---
//----=%+--=@+---=---=-----=+**++**=---------------------=*+****------==---+-----===---
//----*#---*@=---=--==-----=*+#++*+++*=---------------=*#*++#+*+==----+==-+=-----====--
//---=@=---%%----=--=+-----=*+#++*++++***+----------*****+++#**++-----+==-+-------===--
//---%#----%%---==--=+------*+*++*++**+***+**++=+****+==++*+**#-+-----+==-+-------+==--
//--=@=---=%#---==--+*------*++*+*++#+*****++++****+--==*=*****==----===-==-------+==--
//--##----=@*---+=--+*------=++*+*++*++++++*******=-------+***==-----===-==-------+==--
//-=@+----+@=---+=--+#=-----=*+*+*++#++*+++**#*++-+-------+***-+-----+===+--------*==--
//-*@=----*@=---=---+*+------++*+*+*-=++*+***=-+--+--------#**-=-----*====--------*==--
//=%%-----#@---==---=**------++****---------*=----+--------=#=+-----=*==*---------*==--
//=@*-----%@---==---=*#------++*+------=+%@##@+==%%+*+==----+==-----+*+-++++=+++*++==--

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