oj.uz

Submission #173748

# Submission time Handle Problem Language Result Execution time Memory
173748 2020-01-05T09:43:15 Z stefdasca Žarulje (COI15_zarulje) C++14
100 / 100
 167 ms 24056 KB 
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

// #define fisier

using namespace std;

typedef long long ll;


int add(int a, int b)
{
    ll x = a+b;
    if(x >= mod)
        x -= mod;
    if(x < 0)
        x += mod;
    return x;
}
ll mul(ll a, ll b)
{
    return (a*b) % mod;
}

ll pw(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand_seed()
{
    long long a = rng();
    return a;
}
int n, k, val, v[200002];
ll fact[200002], inv[200002];
ll C(int n, int k)
{
    return mul(fact[n], mul(inv[k], inv[n-k]));
}

ll ans[200002], ways, frq[200002], frq2[200002];
vector<pair<int, int> >upds[200002];
int main()
{

    #ifdef fisier
        ifstream f("input.in");
        ofstream g("output.out");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
        cin >> v[i];
    fact[0] = inv[0] = 1;
    for(int i = 1; i <= n; ++i)
    {
        fact[i] = mul(fact[i-1], i);
        inv[i] = pw(fact[i], mod - 2);
    }
    deque<int> d;
    for(int i = n; i >= 1; --i)
    {
        while(!d.empty() && v[d.back()] > v[i])
        {
            --frq[v[d.back()]];
            upds[i].pb({v[d.back()], 1});
            d.pop_back();
        }
        upds[i].pb({v[i], -1});
        frq[v[i]]++;
        d.pb(i);
    }
    d.clear();
    ways = 1;
    for(int i = 1; i <= n; ++i)
    {
        for(int x = 0; x < upds[i].size(); ++x)
        {
            int va = upds[i][x].fi;
            int ct = upds[i][x].se;
            ways = mul(ways, mul(inv[frq[va] + frq2[va]], mul(fact[frq[va]], fact[frq2[va]])));
            frq[va] += ct;
            ways = mul(ways, mul(fact[frq[va] + frq2[va]], mul(inv[frq[va]], inv[frq2[va]])));
        }
        ans[i] = ways;
        while(!d.empty() && v[i] < v[d.back()])
        {
            int va = v[d.back()];
            ways = mul(ways, mul(inv[frq[va] + frq2[va]], mul(fact[frq[va]], fact[frq2[va]])));
            --frq2[va];
            ways = mul(ways, mul(fact[frq[va] + frq2[va]], mul(inv[frq[va]], inv[frq2[va]])));
            d.pop_back();
        }
        int va = v[i];
        ways = mul(ways, mul(inv[frq[va] + frq2[va]], mul(fact[frq[va]], fact[frq2[va]])));
        ++frq2[va];
        ways = mul(ways, mul(fact[frq[va] + frq2[va]], mul(inv[frq[va]], inv[frq2[va]])));
        d.pb(i);
    }
    ways = 1;
    for(; k; --k)
    {
        cin >> val;
        cout << ans[val] << '\n';
    }
    return 0;
}

Compilation message

zarulje.cpp: In function 'int main()':
zarulje.cpp:96:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int x = 0; x < upds[i].size(); ++x)
                        ~~^~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5240 KB Output is correct
3 Correct 7 ms 5240 KB Output is correct
4 Correct 9 ms 5240 KB Output is correct
5 Correct 9 ms 5240 KB Output is correct
6 Correct 8 ms 5240 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 12044 KB Output is correct
2 Correct 98 ms 18424 KB Output is correct
3 Correct 101 ms 18680 KB Output is correct
4 Correct 106 ms 18808 KB Output is correct
5 Correct 108 ms 19276 KB Output is correct
6 Correct 122 ms 20732 KB Output is correct
7 Correct 133 ms 22392 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5112 KB Output is correct
2 Correct 7 ms 5240 KB Output is correct
3 Correct 7 ms 5240 KB Output is correct
4 Correct 9 ms 5240 KB Output is correct
5 Correct 9 ms 5240 KB Output is correct
6 Correct 8 ms 5240 KB Output is correct
7 Correct 55 ms 12044 KB Output is correct
8 Correct 98 ms 18424 KB Output is correct
9 Correct 101 ms 18680 KB Output is correct
10 Correct 106 ms 18808 KB Output is correct
11 Correct 108 ms 19276 KB Output is correct
12 Correct 122 ms 20732 KB Output is correct
13 Correct 133 ms 22392 KB Output is correct
14 Correct 13 ms 5880 KB Output is correct
15 Correct 75 ms 13488 KB Output is correct
16 Correct 141 ms 21756 KB Output is correct
17 Correct 128 ms 20220 KB Output is correct
18 Correct 144 ms 22008 KB Output is correct
19 Correct 133 ms 20332 KB Output is correct
20 Correct 164 ms 22408 KB Output is correct
21 Correct 167 ms 24056 KB Output is correct