oj.uz

Submission #330078

# Submission time Handle Problem Language Result Execution time Memory
330078 2020-11-23T17:24:54 Z fivefourthreeone Žarulje (COI15_zarulje) C++17
100 / 100
 124 ms 27756 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(auto i=(a);i<(b); ++i)
#define uwu(i,a, b) for(auto i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<ttgl, null_type,less<ttgl>, rb_tree_tag,tree_order_statistics_node_update>*/
 
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 62;
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = atan(1);
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 200001;
ll fact[mxN];
ll ifact[mxN];
int arr[mxN];
int r[mxN];
int l[mxN];
vector<int> rr[mxN];
vector<int> rl[mxN];
ll res[mxN];
ll ans = 1;
int cnt[mxN][2];
int n, q;
ll nCr(int n, int r) {
    if(r > n || r < 0)return 0;
    return ((fact[n] * ifact[r])%MOD * ifact[n-r])%MOD;
}
ll rnCr(int n, int r) {
    if(r > n || r < 0)return 0;
    return ((ifact[n] * fact[r])%MOD * fact[n-r])%MOD;
}
void cl(int i, int del) {
    ans = (ans * rnCr(cnt[i][0] + cnt[i][1], cnt[i][0]))%MOD;
    cnt[i][0]+=del;
    ans = (ans * nCr(cnt[i][0] + cnt[i][1], cnt[i][0]))%MOD;
}
void cr(int i, int del) {
    ans = (ans * rnCr(cnt[i][0] + cnt[i][1], cnt[i][0]))%MOD;
    cnt[i][1]+=del;
    ans = (ans * nCr(cnt[i][0] + cnt[i][1], cnt[i][0]))%MOD;
}
int main() {
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>q;
    fact[0] = 1;
    owo(i, 1, mxN) {
        fact[i] = (fact[i-1]*i)%MOD;
    }
    ifact[mxN-1] = modInv(fact[mxN-1]);
    uwu(i, mxN-1, 0) {
        ifact[i] = (ifact[i+1]*(i+1))%MOD;
    }
    int mn = INF;
    owo(i, 0, n) {
        cin>>arr[i];
        arr[i]--;
        if(i) {
            if(arr[i] <= mn) {
                cnt[arr[i]][1]++;
            }
            mn = min(mn, arr[i]);
        }
    }
    owo(i, 0, n) {
        l[i] = i-1;
        while(l[i]>=0 && arr[l[i]] >= arr[i])l[i] = l[l[i]];
        rl[l[i]].senpai(i);
    }
    uwu(i, n, 0) {
        r[i] = i+1;
        while(r[i]<n && arr[r[i]] >= arr[i])r[i] = r[r[i]];
        rr[r[i]].senpai(i);
    }
    owo(i, 0, mxN) {
        //cout<<cnt[i][0]<<" "<<cnt[i][1]<<"\n";
        ans = (ans * nCr(cnt[i][0] + cnt[i][1], cnt[i][0]))%MOD;
    }
    res[0] = ans;
    owo(i, 1, n) {
        cl(arr[i-1], 1);
        for(int k : rr[i-1]) {
            cl(arr[k], -1);
        }
        cr(arr[i], -1);
        for(int k: rl[i]) {
            cr(arr[k], 1);
        }
        res[i] = ans;
    }
    int a;
    while(q--) {
        cin>>a;
        cout<<res[a-1]<<"\n";
    }
    return 0;
}

Compilation message

zarulje.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
zarulje.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12908 KB Output is correct
2 Correct 16 ms 12908 KB Output is correct
3 Correct 16 ms 13036 KB Output is correct
4 Correct 15 ms 13036 KB Output is correct
5 Correct 15 ms 13036 KB Output is correct
6 Correct 15 ms 13036 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 18028 KB Output is correct
2 Correct 68 ms 23148 KB Output is correct
3 Correct 73 ms 23788 KB Output is correct
4 Correct 74 ms 24044 KB Output is correct
5 Correct 75 ms 24300 KB Output is correct
6 Correct 83 ms 25196 KB Output is correct
7 Correct 87 ms 26092 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12908 KB Output is correct
2 Correct 16 ms 12908 KB Output is correct
3 Correct 16 ms 13036 KB Output is correct
4 Correct 15 ms 13036 KB Output is correct
5 Correct 15 ms 13036 KB Output is correct
6 Correct 15 ms 13036 KB Output is correct
7 Correct 44 ms 18028 KB Output is correct
8 Correct 68 ms 23148 KB Output is correct
9 Correct 73 ms 23788 KB Output is correct
10 Correct 74 ms 24044 KB Output is correct
11 Correct 75 ms 24300 KB Output is correct
12 Correct 83 ms 25196 KB Output is correct
13 Correct 87 ms 26092 KB Output is correct
14 Correct 18 ms 13548 KB Output is correct
15 Correct 70 ms 19948 KB Output is correct
16 Correct 108 ms 26476 KB Output is correct
17 Correct 97 ms 25452 KB Output is correct
18 Correct 115 ms 27244 KB Output is correct
19 Correct 99 ms 25452 KB Output is correct
20 Correct 117 ms 26820 KB Output is correct
21 Correct 124 ms 27756 KB Output is correct