oj.uz

Submission #954499

# Submission time Handle Problem Language Result Execution time Memory
954499 2024-03-28T04:48:03 Z vjudge1 Žarulje (COI15_zarulje) C++17
100 / 100
 341 ms 204724 KB 
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
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];
stack<int>KILL[N],l,r;
gp_hash_table<int,int>mp1,mp2;
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 87 ms 183124 KB Output is correct
2 Correct 89 ms 183124 KB Output is correct
3 Correct 88 ms 183120 KB Output is correct
4 Correct 87 ms 183268 KB Output is correct
5 Correct 92 ms 183280 KB Output is correct
6 Correct 87 ms 183520 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 184144 KB Output is correct
2 Correct 276 ms 184656 KB Output is correct
3 Correct 281 ms 184660 KB Output is correct
4 Correct 281 ms 184656 KB Output is correct
5 Correct 289 ms 186828 KB Output is correct
6 Correct 319 ms 203104 KB Output is correct
7 Correct 318 ms 202940 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 183124 KB Output is correct
2 Correct 89 ms 183124 KB Output is correct
3 Correct 88 ms 183120 KB Output is correct
4 Correct 87 ms 183268 KB Output is correct
5 Correct 92 ms 183280 KB Output is correct
6 Correct 87 ms 183520 KB Output is correct
7 Correct 190 ms 184144 KB Output is correct
8 Correct 276 ms 184656 KB Output is correct
9 Correct 281 ms 184660 KB Output is correct
10 Correct 281 ms 184656 KB Output is correct
11 Correct 289 ms 186828 KB Output is correct
12 Correct 319 ms 203104 KB Output is correct
13 Correct 318 ms 202940 KB Output is correct
14 Correct 98 ms 183124 KB Output is correct
15 Correct 196 ms 185168 KB Output is correct
16 Correct 299 ms 188260 KB Output is correct
17 Correct 304 ms 186720 KB Output is correct
18 Correct 331 ms 188652 KB Output is correct
19 Correct 305 ms 188672 KB Output is correct
20 Correct 330 ms 204480 KB Output is correct
21 Correct 341 ms 204724 KB Output is correct