oj.uz

Submission #954520

# Submission time Handle Problem Language Result Execution time Memory
954520 2024-03-28T05:47:38 Z vjudge1 Žarulje (COI15_zarulje) C++17
100 / 100
 318 ms 190644 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize(2)
const int M=1e9+7,N=1<<18;
#define L l.top()
#define R r.top()
int H[N],fac[N],inv[N],res[N],mp1[N],mp2[N];
stack<int>KILL[N],l,r;
int pw(int x,int k=M-2){
    if(!k) return 1;
    int y=pw(x,k/2);
    y=y*y%M;
    if(k&1)y=y*x%M;
    return y;
}
int C(int a,int b){
    return fac[a+b]*inv[b]%M*inv[a]%M;
}
int get(int x){
    return C(mp1[x],mp2[x]);
}
signed main(){
    l.push(0),r.push(0);
    cin.tie(0)->sync_with_stdio(0);
    fac[0]=1;
    for(int i=1;i<N;i++)
        fac[i]=fac[i-1]*i%M;
    inv[N-1]=pw(fac[N-1]);
    res[1]=1;
    for(int i=N;--i;)
        inv[i-1]=inv[i]*i%M;
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>H[i];
    for(int i=n;i>1;mp2[H[i]]++,r.push(H[i--]))
        while(R>H[i])
            KILL[i].push(R),mp2[R]--,r.pop();
    for(int i=2;i<=n;i++) {
        res[i]=res[i-1];
        while(L>H[i-1])
            res[i]=res[i]*pw(get(L))%M,mp1[L]--,res[i]=res[i]*get(L)%M,l.pop();
        res[i]=res[i]*pw(get(R))%M,mp2[R]--,res[i]=res[i]*get(R)%M,r.pop();
        l.push(H[i-1]),res[i]=res[i]*pw(get(L))%M,mp1[L]++,res[i]=res[i]*get(L)%M;
        while(KILL[i].size())
            r.push(KILL[i].top()),res[i]=res[i]*pw(get(R))%M,mp2[R]++,res[i]=res[i]*get(R)%M,KILL[i].pop();
    }
    while(k--){
        int x;
        cin>>x;
        cout<<res[x]<<'\n';
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 185300 KB Output is correct
2 Correct 90 ms 185172 KB Output is correct
3 Correct 90 ms 185172 KB Output is correct
4 Correct 95 ms 185236 KB Output is correct
5 Correct 90 ms 185288 KB Output is correct
6 Correct 90 ms 185220 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 186164 KB Output is correct
2 Correct 274 ms 187280 KB Output is correct
3 Correct 270 ms 187076 KB Output is correct
4 Correct 271 ms 187004 KB Output is correct
5 Correct 273 ms 187536 KB Output is correct
6 Correct 307 ms 189504 KB Output is correct
7 Correct 281 ms 189264 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 185300 KB Output is correct
2 Correct 90 ms 185172 KB Output is correct
3 Correct 90 ms 185172 KB Output is correct
4 Correct 95 ms 185236 KB Output is correct
5 Correct 90 ms 185288 KB Output is correct
6 Correct 90 ms 185220 KB Output is correct
7 Correct 181 ms 186164 KB Output is correct
8 Correct 274 ms 187280 KB Output is correct
9 Correct 270 ms 187076 KB Output is correct
10 Correct 271 ms 187004 KB Output is correct
11 Correct 273 ms 187536 KB Output is correct
12 Correct 307 ms 189504 KB Output is correct
13 Correct 281 ms 189264 KB Output is correct
14 Correct 102 ms 185320 KB Output is correct
15 Correct 189 ms 187712 KB Output is correct
16 Correct 287 ms 189780 KB Output is correct
17 Correct 292 ms 188372 KB Output is correct
18 Correct 303 ms 189780 KB Output is correct
19 Correct 294 ms 188516 KB Output is correct
20 Correct 317 ms 190640 KB Output is correct
21 Correct 318 ms 190644 KB Output is correct