oj.uz

Submission #330980

# Submission time Handle Problem Language Result Execution time Memory
330980 2020-11-27T02:39:47 Z Falcon Žarulje (COI15_zarulje) C++17
100 / 100
 294 ms 141932 KB 
#pragma GCC optimize("O2")

#include <bits/stdc++.h>

#ifdef DEBUG
#include "debug.hpp"
#endif

using namespace std;

#define all(c)              (c).begin(), (c).end()
#define rall(c)             (c).rbegin(), (c).rend()
#define traverse(c, it)     for(auto it = (c).begin(); it != (c).end(); ++it)
#define rep(i, N)           for(int i = 0; i < (N); ++i)
#define rrep(i, N)          for(int i = (N) - 1; i >= 0; --i)
#define rep1(i, N)          for(int i = 1; i <= (N); ++i)
#define rep2(i, s, e)       for(int i = (s); i <= (e); ++i)
#define rep3(i, s, e, d)    for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))

#ifdef DEBUG
#define debug(x...)         { \
                            ++dbg::depth; \
                            string dbg_vals = dbg::to_string(x); \
                            --dbg::depth; \
                            dbg::fprint(__func__, __LINE__, #x, dbg_vals); \
                            }

#define light_debug(x)      { \
                            dbg::light = true; \
                            dbg::dout << __func__ << ":" << __LINE__; \
                            dbg::dout << "  " << #x << " = " << x << endl; \
                            dbg::light = false; \
                            }
#else
#define debug(x...)         42
#define light_debug(x)      42
#endif


using ll = long long;

template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }

template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }


class Modular {
    int value;
    
public:
    static int mod;

    Modular(long long x = 0) {
        value = (int)((x % mod + mod) % mod);
    }

    inline Modular& operator +=(Modular x) {
        value += x.value;
        if(value >= mod) value -= mod;
        return *this;
    }

    inline Modular& operator -=(Modular x) {
        value -= x.value;
        if(value < 0) value += mod;
        return *this;
    }

    inline Modular& operator *=(Modular x) {
        value = int((long long)x.value * value % mod);
        return *this;
    }
    
    // TODO : Make this Extended Euclid to handle composite moduli.
    inline Modular& operator /=(Modular x) {
        return *this *= x.pow(-1);
    }

    inline Modular operator -() const {
        return Modular(-value);
    }

    inline Modular& operator ++() {
        return *this += 1;
    }

    inline Modular& operator --() {
        return *this -= 1;
    }

    inline Modular operator ++(int) {
        Modular t{*this};
        *this += 1;
        return t;
    }

    inline Modular operator --(int) {
        Modular t{*this};
        *this -= 1;
        return t;
    }

    Modular pow(long long n) const { 
        while(n < 0) n += mod - 1;
        Modular v(1), a(value);
        for(; n; a *= a, n >>= 1)
            if(n & 1) v *= a;
        return v;
    }

    inline Modular operator +(Modular x) const {
        return x += *this;
    }

    inline Modular operator -(Modular x) const {
        return *this + (-x);
    }

    inline Modular operator *(Modular x) const {
        return x *= *this;
    }

    inline Modular operator /(Modular x) const {
        return (*this) * x.pow(-1);
    } 

    inline bool operator ==(Modular x) const {
        return value == x.value;
    }

    inline bool operator !=(Modular x) const {
        return value != x.value;
    }

    inline explicit operator int() const {
        return value;
    }

    Modular fact() const { 
        Modular x(1);
        for(int i = 1; i <= value; ++i) x *= i;
        return x;
    }

    friend ostream& operator <<(ostream& os, Modular x) {
        return os << x.value;
    }

    friend istream& operator >>(istream& is, Modular& x) {
        is >> x.value; x.value %= mod; return is;
    }
};

int Modular::mod{1000000007};

array<Modular, 200001> inv;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    #ifdef DEBUG
    freopen("debug", "w", stderr);
    #endif

    rep1(i, 200000) inv[i] = Modular(i).pow(-1);

    int N, K; cin >> N >> K;
    vector<int> A(N); for(int& a : A) cin >> a, --a;

    int M{*max_element(all(A)) + 1};
    vector<int> l(M), r(M);
    Modular ans{1};
    stack<int> p, s;

    auto push_l = [&](int x) {
        p.push(x); ++l[x];
        ans *=  Modular(l[x] + r[x]) * inv[l[x]];
    };

    auto pop_l = [&]() {
        int x{p.top()}; p.pop();
        ans *= Modular(l[x]) * inv[l[x] + r[x]];
        --l[x];
    };

    auto push_r = [&](int x) { 
        s.push(x); ++r[x];
        ans *= Modular(l[x] + r[x]) * inv[r[x]];
    };

    auto pop_r = [&]() {
        int x{s.top()}; s.pop();
        ans *= Modular(r[x]) * inv[l[x] + r[x]];
        --r[x];
    };

    vector<stack<int>> popped(N);
    rrep(i, N) {
        while(!s.empty() && s.top() > A[i]) {
            popped[i].push(s.top()); pop_r();
        }
        push_r(A[i]);
    }

    debug(int(ans), l, r); assert(ans == 1);

    vector<Modular> ways(N);

    rep(i, N) {
        assert(s.top() == A[i]); pop_r();
        while(!popped[i].empty())
            push_r(popped[i].top()), popped[i].pop();
        if(i) {
            while(!p.empty() && p.top() > A[i - 1])
                pop_l();
            push_l(A[i - 1]);
        }
        ways[i] = ans;
        debug(l, r);
    }

    rep(i, K) {
        int P; cin >> P; cout << ways[--P] << '\n';
    }

    #ifdef DEBUG
    dbg::dout << "\nExecution time: " << clock() * 1000 / CLOCKS_PER_SEC  << "ms" << endl;
    #endif

    return 0;
}

Compilation message

zarulje.cpp: In function 'int main()':
zarulje.cpp:35:29: warning: statement has no effect [-Wunused-value]
   35 | #define debug(x...)         42
      |                             ^~
zarulje.cpp:209:5: note: in expansion of macro 'debug'
  209 |     debug(int(ans), l, r); assert(ans == 1);
      |     ^~~~~
zarulje.cpp:35:29: warning: statement has no effect [-Wunused-value]
   35 | #define debug(x...)         42
      |                             ^~
zarulje.cpp:223:9: note: in expansion of macro 'debug'
  223 |         debug(l, r);
      |         ^~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 1132 KB Output is correct
2 Correct 98 ms 1772 KB Output is correct
3 Correct 97 ms 2540 KB Output is correct
4 Correct 98 ms 2668 KB Output is correct
5 Correct 97 ms 2540 KB Output is correct
6 Correct 99 ms 2668 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 69740 KB Output is correct
2 Correct 237 ms 137964 KB Output is correct
3 Correct 230 ms 137964 KB Output is correct
4 Correct 240 ms 138220 KB Output is correct
5 Correct 242 ms 138348 KB Output is correct
6 Correct 240 ms 139244 KB Output is correct
7 Correct 253 ms 140268 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 1132 KB Output is correct
2 Correct 98 ms 1772 KB Output is correct
3 Correct 97 ms 2540 KB Output is correct
4 Correct 98 ms 2668 KB Output is correct
5 Correct 97 ms 2540 KB Output is correct
6 Correct 99 ms 2668 KB Output is correct
7 Correct 173 ms 69740 KB Output is correct
8 Correct 237 ms 137964 KB Output is correct
9 Correct 230 ms 137964 KB Output is correct
10 Correct 240 ms 138220 KB Output is correct
11 Correct 242 ms 138348 KB Output is correct
12 Correct 240 ms 139244 KB Output is correct
13 Correct 253 ms 140268 KB Output is correct
14 Correct 105 ms 8088 KB Output is correct
15 Correct 188 ms 71276 KB Output is correct
16 Correct 279 ms 141228 KB Output is correct
17 Correct 258 ms 139756 KB Output is correct
18 Correct 294 ms 141292 KB Output is correct
19 Correct 265 ms 139500 KB Output is correct
20 Correct 274 ms 141164 KB Output is correct
21 Correct 281 ms 141932 KB Output is correct