Submission #1051344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051344		12345678	Žarulje (COI15_zarulje)	C++17	100 / 100	246 ms	41552 KiB

zarulje

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5, mod=1e9+7;

ll n, q, a[nx], f[nx], inv[nx], res[nx], x;
vector<ll> v[nx];

struct minsegtree
{
    pair<pair<ll, ll>, pair<ll, ll>> d[4*nx];
    pair<pair<ll, ll>, pair<ll, ll>> merge(pair<pair<ll, ll>, pair<ll, ll>> lhs, pair<pair<ll, ll>, pair<ll, ll>> rhs)
    {
        if (lhs.first<=rhs.first)
        {
            if (lhs.second<=rhs.first) return lhs;
            return {lhs.first, rhs.first};
        }
        else
        {
            if (rhs.second<=lhs.first) return rhs;
            return {rhs.first, lhs.first};
        }
    }
    void build(int l, int r, int i)
    {
        if (l==r) return d[i]={{a[l], l}, {1e18, 0}}, void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=merge(d[2*i], d[2*i+1]);
        //cout<<"here "<<l<<' '<<r<<' '<<d[i].first.first<<' '<<d[i].second.first<<'\n';
    }
    pair<pair<ll, ll>, pair<ll, ll>> query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return {{1e18, 0}, {1e18, 0}};
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return merge(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} mn;

struct segtree
{
    ll d[4*nx];
    void build(int l, int r, int i)
    {
        d[i]=1;
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
    }
    void update(int l, int r, int i, int ql, int qr, ll vl)
    {
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return d[i]=(d[i]*vl)%mod, void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr, vl);
        update(md+1, r, 2*i+1, ql, qr, vl);
    }
    void query(int l, int r, int i)
    {
        if (l==r) return res[l]=d[i], void();
        int md=(l+r)/2;
        d[2*i]=(d[2*i]*d[i])%mod;
        d[2*i+1]=(d[2*i+1]*d[i])%mod;
        query(l, md, 2*i);
        query(md+1, r, 2*i+1);
    }
} s;

ll binpow(ll x, ll y)
{
    if (y==0) return 1;
    auto tmp=binpow(x, y/2);
    if (y%2) return ((tmp*tmp)%mod*x)%mod;
    else return (tmp*tmp)%mod;
}

ll combination(ll x, ll y)
{
    return (((f[x+y]*inv[x])%mod)*inv[y])%mod;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q;
    for (int i=1; i<=n; i++) cin>>a[i], v[a[i]].push_back(i);
    mn.build(1, n, 1);
    s.build(1, n, 1);
    //cout<<"debug "<<mn.d[1].first.first<<' '<<mn.d[1].second.first<<'\n';
    f[0]=1;
    for (int i=1; i<=n; i++) f[i]=(f[i-1]*i)%mod;
    inv[n]=binpow(f[n], mod-2);
    for (int i=n-1; i>=1; i--) inv[i]=(inv[i+1]*(i+1))%mod; //cout<<"debug "<<i<<' '<<inv[i]<<' '<<(inv[i]*f[i])%mod<<'\n';
    for (int t=1; t<=200000; t++)
    {
        int sz=v[t].size();
        if (sz<2) continue;
        vector<int> pref(sz), suf(sz);
        for (int i=0; i<sz; i++)
        {
            if (i==0||(v[t][i]-1!=v[t][i-1]&&mn.query(1, n, 1, v[t][i-1]+1, v[t][i]-1).first.first<t)) pref[i]=1;
            else pref[i]=pref[i-1]+1; 
        }
        for (int i=sz-1; i>=0; i--)
        {
            if (i==sz-1||(v[t][i]+1!=v[t][i+1]&&mn.query(1, n, 1, v[t][i]+1, v[t][i+1]-1).first.first<t)) suf[i]=1;
            else suf[i]=suf[i+1]+1; 
        }
        for (int i=0; i<sz-1; i++) 
        {
            auto tmp=mn.query(1, n, 1, v[t][i]+1, v[t][i+1]-1);
            if (v[t][i]+1!=v[t][i+1]&&tmp.first.first>t) s.update(1, n, 1, v[t][i]+1, v[t][i+1]-1, combination(pref[i], suf[i+1]));
            else if (v[t][i]+1!=v[t][i+1]&&tmp.second.first>t) s.update(1, n, 1, tmp.first.second, tmp.first.second, combination(pref[i], suf[i+1]));
        }
        for (int i=1; i<sz-1; i++) if (mn.query(1, n, 1, v[t][i-1]+1, v[t][i+1]-1).first.first>=t) s.update(1, n, 1, v[t][i], v[t][i], combination(pref[i-1], suf[i+1]));
    }
    s.query(1, n, 1);
    while (q--) cin>>x, cout<<res[x]<<'\n';
}

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