oj.uz

Submission #883710

# Submission time Handle Problem Language Result Execution time Memory
883710 2023-12-05T18:56:30 Z vjudge1 Zoltan (COCI16_zoltan) C++17
14 / 140
 330 ms 31676 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 8028 KB Output isn't correct
2 Incorrect 5 ms 8284 KB Output isn't correct
3 Incorrect 6 ms 8284 KB Output isn't correct
4 Correct 5 ms 8028 KB Output is correct
5 Correct 5 ms 8284 KB Output is correct
6 Runtime error 12 ms 16320 KB Execution killed with signal 6
7 Incorrect 6 ms 8284 KB Output isn't correct
8 Incorrect 6 ms 8408 KB Output isn't correct
9 Incorrect 6 ms 8284 KB Output isn't correct
10 Incorrect 6 ms 8284 KB Output isn't correct
11 Incorrect 192 ms 26880 KB Output isn't correct
12 Incorrect 161 ms 24396 KB Output isn't correct
13 Incorrect 149 ms 23476 KB Output isn't correct
14 Incorrect 202 ms 24520 KB Output isn't correct
15 Incorrect 278 ms 28376 KB Output isn't correct
16 Incorrect 330 ms 31676 KB Output isn't correct
17 Incorrect 210 ms 28608 KB Output isn't correct
18 Incorrect 230 ms 28812 KB Output isn't correct
19 Incorrect 240 ms 28604 KB Output isn't correct
20 Incorrect 204 ms 28604 KB Output isn't correct