Submission #330980

#	Time	Username	Problem	Language	Result	Execution time	Memory
330980		Falcon	Žarulje (COI15_zarulje)	C++17	100 / 100	294 ms	141932 KiB

zarulje

#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 (stderr)

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 / 22
• Subtask 2: 38 / 38
• Subtask 3: 40 / 40