oj.uz

Submission #283769

# Submission time Handle Problem Language Result Execution time Memory
283769 2020-08-26T07:06:40 Z 최은수(#5746) Žarulje (COI15_zarulje) C++17
0 / 100
 16 ms 3360 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int mod=1e9+7;
const int mx=200010;
inline int add(int x,int y)
{
    return x+y<mod?x+y:x+y-mod;
}
inline int mul(int x,int y)
{
    return(int)((ll)x*y%mod);
}
inline int pw(int x,int y)
{
    int ret=1;
    while(y>0)
    {
        if(y%2==1)
            ret=mul(ret,x);
        x=mul(x,x);
        y/=2;
    }
    return ret;
}
int fac[mx],invf[mx];
inline int ncr(int n,int r)
{
    return mul(fac[n],mul(invf[n-r],invf[r]));
}
int a[mx];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    fac[0]=1;
    for(int i=0;i++<n;)
        fac[i]=mul(fac[i-1],i);
    invf[n]=pw(fac[n],mod-2);
    for(int i=n;i>0;i--)
        invf[i-1]=mul(invf[i],i);
    for(int i=0;i++<n;)
        cin>>a[i];
    for(int qi=0;qi<k;qi++)
    {
        int x;
        cin>>x;
        vector<pi>vl,vr;
        for(int i=x;i-->1;)
        {
            if(vl.empty()||vl.back().fi!=a[i])
                vl.eb(a[i],1);
            else
                vl.back().se++;
        }
        for(int i=x;i++<n;)
        {
            if(vr.empty()||vr.back().fi!=a[i])
                vr.eb(a[i],1);
            else
                vr.back().se++;
        }
        int ans=1;
        for(int i=0,j=0;i<(int)vl.size();i++)
        {
            while(j<(int)vr.size()&&vr[j].fi>vl[i].fi)
                j++;
            if(j<(int)vr.size()&&vr[j].fi==vl[i].fi)
                ans=mul(ans,ncr(vl[i].se+vr[j].se,vl[i].se));
        }
        cout<<ans<<'\n';
    }
    cout.flush();
    return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 3360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -