oj.uz

Submission #283754

# Submission time Handle Problem Language Result Execution time Memory
283754 2020-08-26T06:56:04 Z 문홍윤(#5764) Žarulje (COI15_zarulje) C++17
0 / 100
 190 ms 5880 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=2e18;
const LL mod=1e9+7;
const int inf=1e9;

LL power(LL a, LL b){
    if(!b)return 1;
    LL ret=power(a, b/2);
    if(b%2)return ret*ret%mod*a%mod;
    return ret*ret%mod;
}
LL fac[200010], invfac[200010], ans[200010], nans=1;
LL C(int a, int b){return fac[a]*invfac[b]%mod*invfac[a-b]%mod;}

int n, q, arr[200010];
int cntl[200010], cntr[200010], link[200010];
bool ch[200010];

int stk[200010], re, cut;

void dfs(int num){
    if(ch[num])return;
    ch[num]=true;
    nans*=power(C(cntl[arr[num]]+cntr[arr[num]], cntl[arr[num]]), mod-2);
    nans%=mod;
    cntr[arr[num]]++;
    nans*=C(cntl[arr[num]]+cntr[arr[num]], cntl[arr[num]]);
    nans%=mod;
    dfs(link[num]);
}

int main(){
    fac[0]=1;
    for(int i=1; i<=200000; i++)fac[i]=fac[i-1]*(LL)i%mod;
    for(int i=0; i<=200000; i++)invfac[i]=power(fac[i], mod-2);
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++)scanf("%d", &arr[i]);
    for(int i=1; i<=n; i++){
        while(re){
            if(arr[stk[re]]<=arr[i]){
                link[stk[re]]=i;
                re--;
            }
            else break;
        }
        stk[++re]=i;
    }
    re=0;
    memset(stk, 0, sizeof stk);
    ch[0]=true;
    dfs(2);
    ans[1]=nans;
    for(int i=2; i<=n; i++){
        nans*=power(C(cntl[arr[i]]+cntr[arr[i]], cntl[arr[i]]), mod-2);
        nans%=mod;
        cntr[arr[i]]--;
        nans*=C(cntl[arr[i]]+cntr[arr[i]], cntl[arr[i]]);
        nans%=mod;
        dfs(i+1);
        while(re){
            if(arr[stk[re]]<arr[i-1]){
                nans*=power(C(cntl[arr[stk[re]]]+cntr[arr[stk[re]]], cntl[arr[stk[re]]]), mod-2);
                nans%=mod;
                cntl[arr[stk[re]]]--;
                nans*=C(cntl[arr[stk[re]]]+cntr[arr[stk[re]]], cntl[arr[stk[re]]]);
                nans%=mod;
                re--;
            }
            else break;
        }
        nans*=power(C(cntl[arr[i-1]]+cntr[arr[i-1]], cntl[arr[i-1]]), mod-2);
        nans%=mod;
        cntl[arr[i-1]]++;
        nans*=C(cntl[arr[i-1]]+cntr[arr[i-1]], cntl[arr[i-1]]);
        nans%=mod;
        stk[++re]=i-1;
        ans[i]=nans;
    }
    for(int i=1; i<=q; i++){
        int a;
        scanf("%d", &a);
        printf("%lld\n", ans[a]);
    }
}

Compilation message

zarulje.cpp: In function 'int main()':
zarulje.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
zarulje.cpp:50:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |     for(int i=1; i<=n; i++)scanf("%d", &arr[i]);
      |                            ~~~~~^~~~~~~~~~~~~~~
zarulje.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   94 |         scanf("%d", &a);
      |         ~~~~~^~~~~~~~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 4216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 190 ms 5880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 4216 KB Output isn't correct
2 Halted 0 ms 0 KB -