oj.uz

Submission #283791

# Submission time Handle Problem Language Result Execution time Memory
283791 2020-08-26T07:21:25 Z 최은수(#5746) Žarulje (COI15_zarulje) C++17
100 / 100
 118 ms 17784 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 r1,int r2)
{
    return mul(fac[r1+r2],mul(invf[r1],invf[r2]));
}
inline int incr(int r1,int r2)
{
    return mul(invf[r1+r2],mul(fac[r1],fac[r2]));
}
int cl[mx],cr[mx];
int cans;
inline void updl(int x,int p)
{
    cans=mul(cans,incr(cl[x],cr[x]));
    cans=mul(cans,ncr(cl[x]+=p,cr[x]));
    return;
}
inline void updr(int x,int p)
{
    cans=mul(cans,incr(cl[x],cr[x]));
    cans=mul(cans,ncr(cl[x],cr[x]+=p));
    return;
}
int a[mx];
int ans[mx];
vector<pi>rev[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];
    vector<int>stl,str;
    cans=1;
    for(int i=n;i>0;i--)
    {
        while(!str.empty()&&str.back()>a[i])
            updr(str.back(),-1),rev[i].eb(str.back(),1),str.pop_back();
        updr(a[i],1);
        rev[i].eb(a[i],-1);
        str.eb(a[i]);
    }
    for(int i=0;i++<n;)
    {
        for(pi&t:rev[i])
            updr(t.fi,t.se);
        ans[i]=cans;
        while(!stl.empty()&&stl.back()>a[i])
            updl(stl.back(),-1),stl.pop_back();
        updl(a[i],1);
        stl.eb(a[i]);
    }
    for(int qi=0;qi<k;qi++)
    {
        int x;
        cin>>x;
        cout<<ans[x]<<'\n';
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 6 ms 5248 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 4 ms 5248 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 10360 KB Output is correct
2 Correct 70 ms 15864 KB Output is correct
3 Correct 71 ms 15736 KB Output is correct
4 Correct 93 ms 15608 KB Output is correct
5 Correct 98 ms 15736 KB Output is correct
6 Correct 79 ms 16376 KB Output is correct
7 Correct 114 ms 17144 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 6 ms 5248 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Correct 4 ms 5248 KB Output is correct
7 Correct 38 ms 10360 KB Output is correct
8 Correct 70 ms 15864 KB Output is correct
9 Correct 71 ms 15736 KB Output is correct
10 Correct 93 ms 15608 KB Output is correct
11 Correct 98 ms 15736 KB Output is correct
12 Correct 79 ms 16376 KB Output is correct
13 Correct 114 ms 17144 KB Output is correct
14 Correct 9 ms 5632 KB Output is correct
15 Correct 56 ms 11384 KB Output is correct
16 Correct 104 ms 17784 KB Output is correct
17 Correct 91 ms 16632 KB Output is correct
18 Correct 109 ms 17656 KB Output is correct
19 Correct 94 ms 16248 KB Output is correct
20 Correct 110 ms 16888 KB Output is correct
21 Correct 118 ms 17656 KB Output is correct