oj.uz

Submission #1004058

# Submission time Handle Problem Language Result Execution time Memory
1004058 2024-06-21T03:47:27 Z saddd Žarulje (COI15_zarulje) C++17
22 / 100
 7 ms 14940 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define int long long
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
const int cox[4] = {1, 0, -1, 0};
const int coy[4] = {0, -1, 0, 1};
const ll mod = 1e9 + 7, pr = 31;
const int mxn = 1e5 + 5, mxq = 1e5 + 5, sq = 400, mxv = 5e4 + 1;
//const int base = (1 <<18);
const ll inf = 1e9 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// have fun!
int n, q;
ll fact[mxn + 1];
int x[mxn + 1], a[mxn + 1];
ll pw(ll a, ll b){
    ll res = 1;
    for(;b;b >>= 1){
        if(b & 1){
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
    }
    return(res);
}
ll choose(int n, int k){
    ll dem = pw((fact[k] * fact[n - k]) % mod, mod - 2);
    return((fact[n] * dem) % mod);
}
namespace sub2{
    void solve(){
        for(int i = 1; i <= q; i++){
            int pos = x[i];
            ll mn = inf;
            map<int, int>cntl, cntr;
            for(int j = pos - 1; j >= 1; j--){
                if(a[j] <= mn){
                    cntl[a[j]]++; mn = a[j];
                }
            }
            mn = inf;
            for(int j = pos + 1; j <= n; j++){
                if(a[j] <= mn){
                    mn = a[j]; cntr[a[j]]++;
                }
            }
            ll ans = 1;
            for(auto j: cntl){
                ans = (ans * choose(j.se + cntr[j.fi], j.se)) % mod;
            }
            cout << ans << "\n";
        }
    }
}
namespace sub3{
    ll res[mxn + 1];
    vt<pii>eventl[mxn + 1], eventr[mxn + 1];
    void solve(){
        vt<int>st;
        map<int, int>cntr, cntl;
        for(int i = n; i >= 1; i--){
            while(sz(st) && a[st.back()] > a[i]){
                eventr[i].pb(mpp(a[st.back()], -1)); st.pop_back();
            }
            eventr[i].pb(mpp(a[i], 1)); st.pb(i);
        }
        for(auto i: st)cntr[a[i]]++;
        st.clear();
        for(int i = 1; i <= n; i++){
            while(sz(st) && a[st.back()] > a[i]){
                eventl[i].pb(mpp(a[st.back()], -1)); st.pop_back();
            }
            eventl[i].pb(mpp(a[i], 1)); st.pb(i);
        }
        ll ans = 1;
        ll mnp = inf;
        for(int i = 1; i <= n; i++){
            for(auto [x, type]: eventr[i]){
                ll rem = pw(choose(cntl[x] + cntr[x], cntr[x]), mod - 2);
                ans = (ans * rem) % mod;
                cntr[x] += -1 * type;
                ans = (ans * choose(cntl[x] + cntr[x], cntr[x])) % mod;
            }
            res[i] = ans;
            for(auto [x, type]: eventl[i]){
                ll rem = pw(choose(cntl[x] + cntr[x], cntr[x]), mod - 2);
                ans = (ans * rem) % mod;
                cntl[x] += type;
                ans = (ans * choose(cntl[x] + cntr[x], cntr[x])) % mod;
            }
        }
        for(int i = 1; i <= q; i++){
            cout << res[x[i]] << "\n";
        }
    }
}
void solve(){
    cin >> n >> q;
    fact[0] = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = (fact[i - 1] * i) % mod;
    }
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= q; i++)cin >> x[i];
    if(q <= 5 || max(n, q) <= 2000)sub2::solve();
    else sub3::solve();
}

 
 
 
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("NOCTURNE.inp", "r", stdin);
    //freopen("NOCTURNE.out", "w", stdout);
    int tt; tt = 1;
    while(tt--){
        solve();
 
    }
    return(0);
}

Compilation message

zarulje.cpp: In function 'void sub3::solve()':
zarulje.cpp:93:12: warning: unused variable 'mnp' [-Wunused-variable]
   93 |         ll mnp = inf;
      |            ^~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6792 KB Output is correct
2 Correct 1 ms 6792 KB Output is correct
3 Correct 7 ms 6840 KB Output is correct
4 Correct 7 ms 6808 KB Output is correct
5 Correct 4 ms 6588 KB Output is correct
6 Correct 6 ms 6748 KB Output is correct

Subtask #2
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7772 KB Output is correct
2 Runtime error 6 ms 14940 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6792 KB Output is correct
2 Correct 1 ms 6792 KB Output is correct
3 Correct 7 ms 6840 KB Output is correct
4 Correct 7 ms 6808 KB Output is correct
5 Correct 4 ms 6588 KB Output is correct
6 Correct 6 ms 6748 KB Output is correct
7 Correct 6 ms 7772 KB Output is correct
8 Runtime error 6 ms 14940 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -