Submission #556078

#	Time	Username	Problem	Language	Result	Execution time	Memory
556078		new_acc	Izbori (COCI22_izbori)	C++14	110 / 110	1544 ms	30288 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],seg[(SS<<1)+10],sp[N],ile[N],n;
pair<int,int> sorted[N];
vi g[N];
void upd(int a,int b){
    for(a+=SS;a>0;a>>=1) seg[a]+=b;
}
int Query(int a,int b){
    int res=0;
    for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
        if(!(a&1)) res+=seg[a+1];
        if(b&1) res+=seg[b-1];
    }
    return res;
}
void clear(int v){
    if(v>(SS<<1) or seg[v]==0) return;
    seg[v]=0;
    clear(v<<1),clear((v<<1)+1);
}
ll big(int x){
    int mini=INT_MAX;
    sp[0]=0;
    for(int i=1;i<=n;i++) sp[i]=sp[i-1]+(t[i]==x?1:-1),mini=min(mini,sp[i]);
    if(mini<0){
        for(int i=0;i<=n;i++) sp[i]+=abs(mini);
    }
    upd(sp[0],1); 
    ll res=0;
    for(int i=1;i<=n;i++){
        res+=(ll)Query(0,sp[i]-1);
        upd(sp[i],1);
    }
    clear(1);
    return res;
}
ll sum(ll a,ll b){
    return a*b-((b*(ll)(b-1))>>1LL);
}
ll small(int x){
    ll res=0;
    for(int i1=0;i1<g[x].size();i1++){
        for(int i2=i1;i2<g[x].size();i2++){
            int p=(i1==0?1:g[x][i1-1]+1),k=(i2==g[x].size()-1?n:g[x][i2+1]-1),ile=i2-i1+1;
            int dl=(ile<<1)-1;
            int pocz=max(p,k-dl+1),prz=max(p,g[x][i2]-dl+1);
            if(prz>g[x][i1]) continue;
            if(pocz>g[x][i1]) res+=sum(g[x][i1]+dl-g[x][i2],g[x][i1]-prz+1);        
            else{
                res+=(ll)(g[x][i1]-pocz)*(ll)(k-g[x][i2]+1);
                res+=sum(k-g[x][i2]+1,pocz-prz+1);
            }
        }
    }
    return res;
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>sorted[i].fi;
        sorted[i].se=i;
    }
    sort(sorted+1,sorted+1+n);
    int curr=0;
    for(int i=1;i<=n;i++){
        if(i==1 or sorted[i].fi!=sorted[i-1].fi) curr++;
        t[sorted[i].se]=curr;
    }
    for(int i=1;i<=n;i++) ile[t[i]]++;
    for(int i=1;i<=n;i++) g[t[i]].push_back(i);
    int p=(int)sqrt(n)<<2;
    ll res=0;
    for(int i=1;i<=curr;i++){
        if(ile[i]>p) res+=big(i);
        else res+=small(i);
    }
    cout<<res<<"\n";
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

Compilation message (stderr)

Main.cpp: In function 'll small(int)':
Main.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i1=0;i1<g[x].size();i1++){
      |                  ~~^~~~~~~~~~~~
Main.cpp:61:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for(int i2=i1;i2<g[x].size();i2++){
      |                       ~~^~~~~~~~~~~~
Main.cpp:62:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             int p=(i1==0?1:g[x][i1-1]+1),k=(i2==g[x].size()-1?n:g[x][i2+1]-1),ile=i2-i1+1;
      |                                             ~~^~~~~~~~~~~~~~~

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