oj.uz

Submission #761926

# Submission time Handle Problem Language Result Execution time Memory
761926 2023-06-20T11:59:10 Z bgnbvnbv Žarulje (COI15_zarulje) C++14
100 / 100
 294 ms 20516 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,k,a[maxN],p[maxN];
vector<int> dq,st;
vector<pli> D;
ll nho[maxN];
ll ans[maxN];
ll luu=1;
ll cnt[2][maxN];
ll f[2*maxN],fr[2*maxN];
ll pw(ll x,ll y)
{
    if(y==0) return 1;
    ll x1=pw(x,y/2);
    x1=x1*x1%mod;
    if(y&1) x1=x1*x%mod;
    return x1;
}
ll C(ll k,ll n)
{
    return f[n]*fr[k]%mod*fr[n-k]%mod;
}
void c(ll t,ll x,ll v)
{
    luu=luu*pw(C(cnt[t][x],cnt[t][x]+cnt[1-t][x]),mod-2)%mod;
    cnt[t][x]+=v;
    luu=luu*C(cnt[t][x],cnt[t][x]+cnt[1-t][x])%mod;
}
void rollback(ll x)
{
    while(D.size()>x)
    {
        if(D.back().fi==0)
        {
            dq.pb(D.back().se);
            c(1,D.back().se,1);
        }
        else
        {
            dq.pop_back();
            c(1,D.back().se,-1);
        }
        D.pop_back();
    }
}
void solve()
{
    cin >> n >> k;
    for(int i=1;i<=n;i++) cin >> a[i];
    //for(int i=1;i<=k;i++) cin >> p[i];
    f[0]=1;
    for(ll i=1;i<=2*n;i++)
    {
        f[i]=f[i-1]*i%mod;
    }
    fr[2*n]=pw(f[2*n],mod-2);
    for(ll i=2*n-1;i>=0;i--)
    {
        fr[i]=fr[i+1]*(i+1)%mod;
    }
    for(int i=n;i>=1;i--)
    {
        while(dq.size()>0&&a[i]<dq.back())
        {
            D.pb({0,dq.back()});
            c(1,dq.back(),-1);
            dq.pop_back();
        }
        dq.pb(a[i]);
        D.pb({1,dq.back()});
        c(1,dq.back(),1);
        nho[i]=D.size();
    }

    for(int i=1;i<=n;i++)
    {
        rollback(nho[i+1]);
        if(i>1)
        {
            while(st.size()>0&&a[i-1]<st.back())
            {
                c(0,st.back(),-1);
                st.pop_back();
            }
            st.pb(a[i-1]);
            c(0,st.back(),1);
        }
        ans[i]=luu;
    }
    for(int i=1;i<=k;i++)
    {
        ll p;
        cin >> p;
        cout << ans[p]<<'\n';
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

zarulje.cpp: In function 'void rollback(ll)':
zarulje.cpp:41:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   41 |     while(D.size()>x)
      |           ~~~~~~~~^~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 3 ms 480 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 3 ms 612 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 7868 KB Output is correct
2 Correct 250 ms 14860 KB Output is correct
3 Correct 259 ms 15032 KB Output is correct
4 Correct 261 ms 15264 KB Output is correct
5 Correct 265 ms 15724 KB Output is correct
6 Correct 266 ms 17220 KB Output is correct
7 Correct 273 ms 18872 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 3 ms 480 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 3 ms 612 KB Output is correct
7 Correct 132 ms 7868 KB Output is correct
8 Correct 250 ms 14860 KB Output is correct
9 Correct 259 ms 15032 KB Output is correct
10 Correct 261 ms 15264 KB Output is correct
11 Correct 265 ms 15724 KB Output is correct
12 Correct 266 ms 17220 KB Output is correct
13 Correct 273 ms 18872 KB Output is correct
14 Correct 15 ms 1376 KB Output is correct
15 Correct 143 ms 9392 KB Output is correct
16 Correct 272 ms 18184 KB Output is correct
17 Correct 276 ms 16720 KB Output is correct
18 Correct 285 ms 18524 KB Output is correct
19 Correct 279 ms 16696 KB Output is correct
20 Correct 287 ms 18844 KB Output is correct
21 Correct 294 ms 20516 KB Output is correct