oj.uz

Submission #556078

# Submission time Handle Problem Language Result Execution time Memory
556078 2022-05-02T10:21:19 Z new_acc Izbori (COCI22_izbori) C++14
110 / 110
 1544 ms 30288 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 15 ms 23764 KB Output is correct
3 Correct 14 ms 23764 KB Output is correct
4 Correct 16 ms 23852 KB Output is correct
5 Correct 16 ms 23804 KB Output is correct
6 Correct 13 ms 23892 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 15 ms 23764 KB Output is correct
3 Correct 14 ms 23764 KB Output is correct
4 Correct 16 ms 23852 KB Output is correct
5 Correct 16 ms 23804 KB Output is correct
6 Correct 13 ms 23892 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23744 KB Output is correct
9 Correct 16 ms 23900 KB Output is correct
10 Correct 14 ms 23948 KB Output is correct
11 Correct 15 ms 23896 KB Output is correct
12 Correct 14 ms 23948 KB Output is correct
13 Correct 13 ms 23928 KB Output is correct
14 Correct 16 ms 23880 KB Output is correct
15 Correct 14 ms 23860 KB Output is correct
16 Correct 14 ms 24020 KB Output is correct
17 Correct 16 ms 23856 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 26632 KB Output is correct
2 Correct 55 ms 27404 KB Output is correct
3 Correct 35 ms 25976 KB Output is correct
4 Correct 55 ms 27500 KB Output is correct
5 Correct 59 ms 27784 KB Output is correct
6 Correct 60 ms 27932 KB Output is correct
7 Correct 60 ms 27968 KB Output is correct
8 Correct 66 ms 27940 KB Output is correct
9 Correct 61 ms 27936 KB Output is correct
10 Correct 62 ms 27968 KB Output is correct
11 Correct 54 ms 29436 KB Output is correct

Subtask #4
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 15 ms 23764 KB Output is correct
3 Correct 14 ms 23764 KB Output is correct
4 Correct 16 ms 23852 KB Output is correct
5 Correct 16 ms 23804 KB Output is correct
6 Correct 13 ms 23892 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23744 KB Output is correct
9 Correct 16 ms 23900 KB Output is correct
10 Correct 14 ms 23948 KB Output is correct
11 Correct 15 ms 23896 KB Output is correct
12 Correct 14 ms 23948 KB Output is correct
13 Correct 13 ms 23928 KB Output is correct
14 Correct 16 ms 23880 KB Output is correct
15 Correct 14 ms 23860 KB Output is correct
16 Correct 14 ms 24020 KB Output is correct
17 Correct 16 ms 23856 KB Output is correct
18 Correct 49 ms 26632 KB Output is correct
19 Correct 55 ms 27404 KB Output is correct
20 Correct 35 ms 25976 KB Output is correct
21 Correct 55 ms 27500 KB Output is correct
22 Correct 59 ms 27784 KB Output is correct
23 Correct 60 ms 27932 KB Output is correct
24 Correct 60 ms 27968 KB Output is correct
25 Correct 66 ms 27940 KB Output is correct
26 Correct 61 ms 27936 KB Output is correct
27 Correct 62 ms 27968 KB Output is correct
28 Correct 54 ms 29436 KB Output is correct
29 Correct 54 ms 29400 KB Output is correct
30 Correct 23 ms 25496 KB Output is correct
31 Correct 32 ms 26852 KB Output is correct
32 Correct 72 ms 30288 KB Output is correct
33 Correct 41 ms 27084 KB Output is correct
34 Correct 35 ms 27168 KB Output is correct
35 Correct 26 ms 26072 KB Output is correct
36 Correct 21 ms 25236 KB Output is correct
37 Correct 21 ms 25556 KB Output is correct
38 Correct 115 ms 28944 KB Output is correct
39 Correct 121 ms 28812 KB Output is correct
40 Correct 122 ms 28932 KB Output is correct
41 Correct 118 ms 28816 KB Output is correct
42 Correct 115 ms 29036 KB Output is correct
43 Correct 226 ms 29636 KB Output is correct
44 Correct 227 ms 29516 KB Output is correct
45 Correct 235 ms 29476 KB Output is correct
46 Correct 229 ms 29532 KB Output is correct
47 Correct 224 ms 29516 KB Output is correct
48 Correct 183 ms 27100 KB Output is correct
49 Correct 175 ms 27180 KB Output is correct
50 Correct 1544 ms 29936 KB Output is correct
51 Correct 1532 ms 29836 KB Output is correct
52 Correct 112 ms 27080 KB Output is correct
53 Correct 113 ms 27000 KB Output is correct
54 Correct 212 ms 27104 KB Output is correct