oj.uz

Submission #173752

# Submission time Handle Problem Language Result Execution time Memory
173752 2020-01-05T09:57:54 Z stefdasca Žarulje (COI15_zarulje) C++14
100 / 100
 137 ms 23988 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[n] = pw(fact[n], mod - 2);
    for(int i = n-1; i >= 1; --i)
        inv[i] = mul(inv[i+1], i+1);
    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);
    }
    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 6 ms 5116 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5240 KB Output is correct
4 Correct 7 ms 5212 KB Output is correct
5 Correct 7 ms 5240 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 11896 KB Output is correct
2 Correct 122 ms 18552 KB Output is correct
3 Correct 72 ms 18628 KB Output is correct
4 Correct 68 ms 18816 KB Output is correct
5 Correct 79 ms 19068 KB Output is correct
6 Correct 93 ms 20844 KB Output is correct
7 Correct 114 ms 22396 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5116 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5240 KB Output is correct
4 Correct 7 ms 5212 KB Output is correct
5 Correct 7 ms 5240 KB Output is correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 40 ms 11896 KB Output is correct
8 Correct 122 ms 18552 KB Output is correct
9 Correct 72 ms 18628 KB Output is correct
10 Correct 68 ms 18816 KB Output is correct
11 Correct 79 ms 19068 KB Output is correct
12 Correct 93 ms 20844 KB Output is correct
13 Correct 114 ms 22396 KB Output is correct
14 Correct 14 ms 5892 KB Output is correct
15 Correct 61 ms 13432 KB Output is correct
16 Correct 113 ms 21752 KB Output is correct
17 Correct 97 ms 20152 KB Output is correct
18 Correct 115 ms 22008 KB Output is correct
19 Correct 102 ms 20284 KB Output is correct
20 Correct 128 ms 22392 KB Output is correct
21 Correct 137 ms 23988 KB Output is correct