oj.uz

Submission #1051344

# Submission time Handle Problem Language Result Execution time Memory
1051344 2024-08-10T04:51:33 Z 12345678 Žarulje (COI15_zarulje) C++17
100 / 100
 246 ms 41552 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 3 ms 14816 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 24460 KB Output is correct
2 Correct 146 ms 36884 KB Output is correct
3 Correct 209 ms 37108 KB Output is correct
4 Correct 232 ms 37544 KB Output is correct
5 Correct 241 ms 38184 KB Output is correct
6 Correct 150 ms 39000 KB Output is correct
7 Correct 106 ms 39988 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 3 ms 14816 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 2 ms 14684 KB Output is correct
7 Correct 101 ms 24460 KB Output is correct
8 Correct 146 ms 36884 KB Output is correct
9 Correct 209 ms 37108 KB Output is correct
10 Correct 232 ms 37544 KB Output is correct
11 Correct 241 ms 38184 KB Output is correct
12 Correct 150 ms 39000 KB Output is correct
13 Correct 106 ms 39988 KB Output is correct
14 Correct 11 ms 17240 KB Output is correct
15 Correct 108 ms 26280 KB Output is correct
16 Correct 184 ms 40024 KB Output is correct
17 Correct 195 ms 38628 KB Output is correct
18 Correct 232 ms 40528 KB Output is correct
19 Correct 246 ms 39248 KB Output is correct
20 Correct 184 ms 40700 KB Output is correct
21 Correct 119 ms 41552 KB Output is correct