oj.uz

Submission #283771

# Submission time Handle Problem Language Result Execution time Memory
283771 2020-08-26T07:06:53 Z 문홍윤(#5764) Žarulje (COI15_zarulje) C++17
100 / 100
 407 ms 12024 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;

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++)arr[i]=200001-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:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |         scanf("%d", &a);
      |         ~~~~~^~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 4216 KB Output is correct
2 Correct 66 ms 4216 KB Output is correct
3 Correct 72 ms 4472 KB Output is correct
4 Correct 69 ms 4344 KB Output is correct
5 Correct 65 ms 4344 KB Output is correct
6 Correct 66 ms 4320 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 5880 KB Output is correct
2 Correct 333 ms 8188 KB Output is correct
3 Correct 377 ms 8184 KB Output is correct
4 Correct 364 ms 8324 KB Output is correct
5 Correct 352 ms 8568 KB Output is correct
6 Correct 360 ms 9720 KB Output is correct
7 Correct 362 ms 10360 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 4216 KB Output is correct
2 Correct 66 ms 4216 KB Output is correct
3 Correct 72 ms 4472 KB Output is correct
4 Correct 69 ms 4344 KB Output is correct
5 Correct 65 ms 4344 KB Output is correct
6 Correct 66 ms 4320 KB Output is correct
7 Correct 209 ms 5880 KB Output is correct
8 Correct 333 ms 8188 KB Output is correct
9 Correct 377 ms 8184 KB Output is correct
10 Correct 364 ms 8324 KB Output is correct
11 Correct 352 ms 8568 KB Output is correct
12 Correct 360 ms 9720 KB Output is correct
13 Correct 362 ms 10360 KB Output is correct
14 Correct 83 ms 4600 KB Output is correct
15 Correct 226 ms 7800 KB Output is correct
16 Correct 397 ms 11256 KB Output is correct
17 Correct 382 ms 9848 KB Output is correct
18 Correct 407 ms 11512 KB Output is correct
19 Correct 378 ms 9720 KB Output is correct
20 Correct 399 ms 11128 KB Output is correct
21 Correct 403 ms 12024 KB Output is correct