Submission #883710

#	Time	Username	Problem	Language	Result	Execution time	Memory
883710		vjudge1	Zoltan (COCI16_zoltan)	C++17	14 / 140	330 ms	31676 KiB

zoltan

#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=2e5+100;
#else
    const int lim=2e5+100;
#endif

#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define pb push_back

const int mod=1e9+7;
using pii=pair<int,int>;

int sum(long int i,long int j){
    return (i+j<mod?i+j:i+j-mod);
}
int mul(long int i,long int j){
    return (i*j)%mod;
}
int expo(long int i,long int j){
    int ans=1;
    while(j){
        if(j&1){
            ans=mul(ans,i);
        }
        i=mul(i,i);
        j>>=1;
    }
    return ans;
}

struct segtree{
    int n;
    pii tree[4*lim];
    segtree(int n):n(n){
        fill(tree,tree+4*n,pii{0,0});
    }
    inline pii merge(pii v1,pii v2){
        if(v1.first>v2.first){
            return v1;
        }
        if(v2.first>v1.first){
            return v2;
        }
        return pii{v1.first,sum(v1.second,v2.second)};
    }
    int P;
    pii VAL;
    pii update(int l,int r,int node){
        if(P<l||r<P){
            return tree[node];
        }
        if(l==r){
            return tree[node]=merge(tree[node],VAL);
        }
        int mid=(l+r)>>1,child=node<<1;
        return tree[node]=merge(update(l,mid,child),update(mid+1,r,child|1));
    }
    pii query(int l,int r,int node){
        if(P<=l){
            return {0,0};
        }
        if(r<P){
            return tree[node];
        }
        int mid=(l+r)>>1,child=node<<1;
        return merge(query(l,mid,child),query(mid+1,r,child|1));
    }
    void update(int p,pii val){
        P=p,VAL=val;
        update(0,n-1,1);
    }
    pii query(int p){
        P=p;
        return query(0,n-1,1);
    }
};

int perm[lim],iperm[lim];
int ncr(long int n,long int r){
    if(n<r)return 0;
    if(n<0||r<0)return 0;
    return mul(perm[n],mul(perm[n-r],perm[r]));
}

int formula(int n){
    return mul(n,expo(2,n-1));
}

inline void solve(){
    perm[0]=1;
    for(int i=1;i<lim;i++){
        perm[i]=mul(perm[i],i);
    }
    iperm[lim-1]=expo(perm[lim-1],mod-2);
    for(int i=lim-2;0<=i;i--){
        iperm[i]=mul(iperm[i+1],i);
    }
    int n;
    cin>>n;
    vector<pii>a;
    set<int>all;
    for(int i=0;i<n;i++){
        int tem;
        cin>>tem;
        if(!a.size()||a.back().first!=tem){
            a.pb(pii{tem,1});
        }else{
            a.back().second++;
        }
        all.insert(tem);
    }
    map<int,int>to;
    int counter=0;
    for(int i:all){
        to[i]=counter++;
    }
    for(int i=0;i<n;i++){
        a[i].first=to[a[i].first];
    }
    deque<pii> d{a[0]};
    for(int i=1;i<a.size();i++){
        d.pb(a[i]);
        d.push_front(a[i]);
    }
    segtree st(counter);
    for(int i=0;i<d.size();i++){
        pii too=st.query(d[i].first);
        if(too==pii{0,0}){
            too={1,formula(d[i].second)};
        }else{
            too.first++;
            too.second=mul(too.second,formula(d[i].second));
        }
        //cerr<<d[i]<<" {"<<too.first<<" "<<too.second<<"}\n";
        st.update(d[i].first,too);
    }
    pii ans=st.query(counter);
    cout<<ans.first<<" "<<ans.second<<"\n";
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else
    //freopen("grass.in","r",stdin);
    //freopen("grass.out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Compilation message (stderr)

zoltan.cpp: In function 'void solve()':
zoltan.cpp:125:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     for(int i=1;i<a.size();i++){
      |                 ~^~~~~~~~~
zoltan.cpp:130:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     for(int i=0;i<d.size();i++){
      |                 ~^~~~~~~~~

• Subtask 1: 14 / 140