제출 #1084327

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1084327		vjudge1	Žarulje (COI15_zarulje)	C++17	0 / 100	12 ms	8028 KiB

zarulje

#include <bits/stdc++.h>

using namespace std;
long long n,mod = 1000000000+7;
long long niza[200002];
bool visited[2002][2002];
long long dp[2002][2002];

long long f(long long l,long long r)
{
    if (l==0 && r==n+1) return 1;
    if (visited[l][r]) return dp[l][r];

    long long odg = 0;
    if (l>0 && (r>n || niza[l]>=niza[r])) odg += (f(l-1,r))%mod;
    if (r<=n && (l==0 || niza[r]>=niza[l])) odg += (f(l,r+1))%mod;
    odg%=mod;

    visited[l][r]=true;
    dp[l][r]=odg;
    return odg;
}

long long fact[200002],inv_fact[200002];

long long kombinacii(long long a,long long b)
{
    //cout<< "ulava a="<<a<<" b="<<b<<endl;
    if (a==0 || a>=b) return 0;
    return (((fact[b]*inv_fact[a])%mod) * inv_fact[b-a])%mod;
}

long long cestota[200001];
long long levo_pojavuvanja[200001];
bool used[200001];

long long subtask2(long long k)
{
    long long l = k-1, r = k+1;
    long long m = min(niza[l],niza[r]);
    memset(cestota,0,sizeof(cestota));
    memset(levo_pojavuvanja,0,sizeof(levo_pojavuvanja));
    memset(used,0,sizeof(used));
    levo_pojavuvanja[niza[l]]++;
    cestota[niza[l]]++;
    cestota[niza[r]]++;

    long long odg = 0;
    while(l>0 || r<=n)
    {
        //cout<<"l="<<l<<" r="<<r<<endl;
        if (l>0 && r<=n && niza[l]>niza[r])
        {
            l--;
            levo_pojavuvanja[niza[l]]++;
            cestota[niza[l]]++;
            continue;
        }
        if (l>0 && r<=n && niza[l]<niza[r])
        {
            r++;
            cestota[niza[r]]++;
            continue;
        }

        if (l>0 && niza[l]<m)
        {
            odg += (kombinacii(levo_pojavuvanja[m],cestota[m]))%mod;
            used[m]=true;
            m = niza[l];
        }
        if (l>0)
        {
            l--;
            if (l>0) levo_pojavuvanja[niza[l]]++;
            if (l>0) cestota[niza[l]]++;
        }
        if (r<=n)
        {
            r++;
            if (r<=n) cestota[niza[r]]++;
        }


    }
    if (m>0 && !used[m]) odg+=(kombinacii(levo_pojavuvanja[m],cestota[m]))%mod;

    if (odg==0) odg=1;
    return odg;
}

long long mod_inverse(long long a, long long m) {
    long long result = 1;
    long long power = m - 2;
    while (power) {
        if (power % 2 == 1) {
            result = (result * a) % m;
        }
        a = (a * a) % m;
        power /= 2;
    }
    return result;
}

void sredi_fact()
{
    fact[0]=1;
    for (long long i=1;i<=200000;i++)
        fact[i]=(fact[i-1]*i)%mod;

    inv_fact[200000] = mod_inverse(fact[200000],mod);

    for (long long i=200000-1;i>=0;i--)
        inv_fact[i] = (inv_fact[i+1]*(i+1))%mod;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    sredi_fact();
    long long m;
    cin>>n>>m;
    for (long long i=1;i<=n;i++) cin>>niza[i];

    for (long long i=0;i<m;i++)
    {
        long long a;
        cin>>a;
        if (n<=2000 && false) cout<<f(a-1,a+1)<<endl;
        else cout<<subtask2(a)<<endl;
        //system("pause");
    }

    return 0;
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 38
• Subtask 3: 0 / 40