Submission #393472

#	Time	Username	Problem	Language	Result	Execution time	Memory
393472		dutinmeow	Growing Trees (BOI11_grow)	C++14	100 / 100	189 ms	6072 KiB

grow

#include <iostream>
#include <iomanip>

#include <cstdio>
#include <cstdint>
#include <cstddef>
#include <cmath>
#include <cstring>
#include <cassert>
#include <ctime>

#include <algorithm>
#include <utility>
#include <functional>
#include <chrono>

#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>

//#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx2")
//#pragma GCC optimize("unroll-loops")
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;

// data types
typedef int_fast8_t  int8;
typedef int_fast16_t int16;
typedef int_fast32_t int32;
typedef int_fast64_t int64;
typedef int_fast64_t ll;

typedef uint_fast8_t  uint8;
typedef uint_fast16_t uint16;
typedef uint_fast32_t uint32;
typedef uint_fast16_t uint64;
typedef uint_fast16_t ull;

typedef ptrdiff_t ptrdif;
typedef size_t uintn;

typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll>   pll;
typedef pair<ll, pll>  plll;

template<typename T> 
using Iterator = typename T::iterator;

template<class K, class V> 
using ordered_map = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>; 

template<class K> 
using ordered_set = ordered_map<K, null_type>; 

// constants
const int inf = 2000000011;
const ll  llinf = 999999999999999989;
const int MOD = 1e9 + 7;
const double PI = acos(-1);

const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, 1, 0, -1};

// macros
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define EB emplace_back
#define EF emplace_front
#define MP make_pair
#define FF first
#define SS second

// hash
namespace hash0 {
    struct chash { 
        const uint64_t C = ll(2e18*PI)+71; 
        const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count(); 

        inline ll operator()(ll x) const { return __builtin_bswap64((x ^ RANDOM) * C); }

        inline ll operator()(pii p) const { return __builtin_bswap64((p.FF ^ RANDOM) * C) + p.SS; }
    };

    template<class K, class V> 
    using fast_map = gp_hash_table<K, V, chash>;

    template<class K> 
    using fast_set = fast_map<K, null_type>;
}

using namespace hash0;

// functions
namespace functions {
    inline void stop() { assert(0); }

    template<typename T>
    inline void sort(T& c) { sort(c.begin(), c.end()); }

    template<typename T, typename S> 
    inline void sort(T& c, S s) { sort(c.begin(), c.end(), s); }

    template<typename T>
    inline void reverse(T& c) { reverse(c.begin(), c.end()); }

    // lambda template: [](const C& a, const C& b) { return a > b; }

    inline ll  ceil0(ll a, ll b) { 
        return a / b + ((a ^ b) > 0 && a % b); 
    } 

    inline ll floor0(ll a, ll b) { 
        return a / b - ((a ^ b) < 0 && a % b); 
    }

    ll pow0(ll a, ll b) { 
        ll res = 1; 
        for (a %= MOD; b; b >>= 1) { 
            if(b & 1) res = res * a % MOD; 
            a = a * a % MOD; 
        } 
        return res; 
    }

    template<typename T>
    string binary(T b) {
        string res = "";
        for (int i = sizeof(T) * 8 - 1; i >= 0; i--)
            res += (b & (1 << i) ? '1' : '0');
        return res;
    }

    template<typename T>
    string binary(T b, int k) {
        string res = "";
        for (int i = k; i >= 0; i--)
            res += ((b & (1 << i)) ? '1' : '0');
        return res;
    }
}

using namespace functions;

// operators
namespace operators {
    namespace pairs {
        template<typename T1, typename T2>
        pair<T1, T2> operator+(const pair<T1, T2>& a, const pair<T1, T2>& b) { return MP(a.FF + b.FF, a.SS + b.SS); }

        template<typename T1, typename T2>
        pair<T1, T2> operator-(const pair<T1, T2>& a, const pair<T1, T2>& b) { return MP(a.FF - b.FF, a.SS - b.SS); }

        template<typename T1, typename T2>
        pair<T1, T2> operator*(const pair<T1, T2>& a, const pair<T1, T2>& b) { return MP(a.FF * b.FF, a.SS * b.SS); }

        template<typename T1, typename T2>
        pair<T1, T2> operator/(const pair<T1, T2>& a, const pair<T1, T2>& b) { return MP(a.FF / b.FF, a.SS / b.SS); }

        template<typename T1, typename T2>
        pair<T1, T2> operator%(const pair<T1, T2>& a, const pair<T1, T2>& b) { return MP(a.FF % b.FF, a.SS % b.SS); }

        template<typename T1, typename T2>
        pair<T1, T2> operator&(const pair<T1, T2>& a, const pair<T1, T2>& b) { return MP(a.FF & b.FF, a.SS & b.SS); }

        template<typename T1, typename T2>  
        pair<T1, T2> operator|(const pair<T1, T2>& a, const pair<T1, T2>& b) { return MP(a.FF | b.FF, a.SS | b.SS); }

        template<typename T1, typename T2>
        pair<T1, T2> operator^(const pair<T1, T2>& a, const pair<T1, T2>& b) { return MP(a.FF ^ b.FF, a.SS ^ b.SS); }

        template<typename T1, typename T2>
        pair<T1, T2> operator-(const pair<T1, T2>& a) { return MP(-a.FF, -a.SS); }

        template<typename T1, typename T2>
        pair<T1, T2> operator~(const pair<T1, T2>& a) { return MP(~a.FF, ~a.SS); }
    }

    using namespace pairs;

    namespace vectors {
        namespace vector_scalar {
            template<typename T>
            vector<T> operator+(const vector<T>& v, const T& c) { 
                vector<T> v0(v.begin(), v.end());
                for (auto& x : v0) 
                    x += c; 
                return v0; 
            }

            template<typename T>
            vector<T> operator-(const vector<T>& v, const T& c) { 
                vector<T> v0(v.begin(), v.end());
                for (auto& x : v0) 
                    x -= c; 
                return v0; 
            }

            template<typename T>
            vector<T> operator*(const vector<T>& v, const T& c) { 
                vector<T> v0(v.begin(), v.end());
                for (auto& x : v0) 
                    x *= c; 
                return v0; 
            }

            template<typename T>
            vector<T> operator/(const vector<T>& v, const T& c) { 
                vector<T> v0(v.begin(), v.end());
                for (auto& x : v0) 
                    x /= c; 
                return v0; 
            }

            template<typename T>
            vector<T> operator%(const vector<T>& v, const T& c) { 
                vector<T> v0(v.begin(), v.end());
                for (auto& x : v0) 
                    x %= c; 
                return v0; 
            }

            template<typename T>
            vector<T> operator&(const vector<T>& v, const T& c) { 
                vector<T> v0(v.begin(), v.end());
                for (auto& x : v0) 
                    x &= c; 
                return v0; 
            }

            template<typename T>
            vector<T> operator|(const vector<T>& v, const T& c) { 
                vector<T> v0(v.begin(), v.end());
                for (auto& x : v0) 
                    x |= c; 
                return v0; 
            }

            template<typename T>
            vector<T> operator^(const vector<T>& v, const T& c) { 
                vector<T> v0(v.begin(), v.end());
                for (auto& x : v0) 
                    x ^= c; 
                return v0; 
            }
            
            template<typename T>
            vector<T> operator-(const vector<T>& v) {
                vector<T> v0(v.begin(), v.end());
                for (auto& x : v0)
                    x = -x;
                return v0;
            }

            template<typename T>
            vector<T> operator~(const vector<T>& v) {
                vector<T> v0(v.begin(), v.end());
                for (auto& x : v0)
                    x = ~x;
                return v0;
            }
        }

        using namespace vector_scalar;

        namespace vector_vector {
            template<typename T>
            vector<T> operator+(const vector<T>& v0, const vector<T>& v1) {
                assert(v0.size() == v1.size());
                vector<T> v (v0.size());
                for (int i = 0; i < v.size(); i++)
                    v[i] = v0[i] + v1[i];
                return v;
            }

            template<typename T>
            vector<T> operator-(const vector<T>& v0, const vector<T>& v1) {
                assert(v0.size() == v1.size());
                vector<T> v (v0.size());
                for (int i = 0; i < v.size(); i++)
                    v[i] = v0[i] - v1[i];
                return v;
            }

            template<typename T>
            vector<T> operator*(const vector<T>& v0, const vector<T>& v1) {
                assert(v0.size() == v1.size());
                vector<T> v (v0.size());
                for (int i = 0; i < v.size(); i++)
                    v[i] = v0[i] * v1[i];
                return v;
            }

            template<typename T>
            vector<T> operator/(const vector<T>& v0, const vector<T>& v1) {
                assert(v0.size() == v1.size());
                vector<T> v (v0.size());
                for (int i = 0; i < v.size(); i++)
                    v[i] = v0[i] / v1[i];
                return v;
            }

            template<typename T>
            vector<T> operator%(const vector<T>& v0, const vector<T>& v1) {
                assert(v0.size() == v1.size());
                vector<T> v (v0.size());
                for (int i = 0; i < v.size(); i++)
                    v[i] = v0[i] % v1[i];
                return v;
            }

            template<typename T>
            vector<T> operator&(const vector<T>& v0, const vector<T>& v1) {
                assert(v0.size() == v1.size());
                vector<T> v (v0.size());
                for (int i = 0; i < v.size(); i++)
                    v[i] = v0[i] & v1[i];
                return v;
            }

            template<typename T>
            vector<T> operator|(const vector<T>& v0, const vector<T>& v1) {
                assert(v0.size() == v1.size());
                vector<T> v (v0.size());
                for (int i = 0; i < v.size(); i++)
                    v[i] = v0[i] | v1[i];
                return v;
            }

            template<typename T>
            vector<T> operator^(const vector<T>& v0, const vector<T>& v1) {
                assert(v0.size() == v1.size());
                vector<T> v (v0.size());
                for (int i = 0; i < v.size(); i++)
                    v[i] = v0[i] ^ v1[i];
                return v;
            }
        }

        using namespace vector_vector;
    }

    using namespace vectors;


}

using namespace operators;

// input
namespace input {
    void filein(const string FILENAME) { freopen(FILENAME.c_str(), "r", stdin); }

    template<typename T1, typename T2>
    inline istream& operator>>(istream& is, pair<T1, T2>& p) {
        return is >> p.FF >> p.SS;
    }

    template<typename T>
    inline istream& operator>>(istream& is, vector<T>& v) { 
        for (auto& x : v)
            is >> x;
        return is;
    }

    inline void read() {}

    template<typename T, typename... U> 
    inline void read(T& F, U&... S) {
        cin >> F;
        read(S...);
    }

    template<typename T>
    void read(T* a, int n) {
        for (int i = 0; i < n; i++)
            cin >> a[i];
    }

    template<typename T>
    void read(T* a, int l, int r) {
        for (int i = l; i <= r; i++)
            cin >> a[i];
    }

    template<typename T> 
    void read(vector<T>& v, int n) {
        assert(n < v.size());
        for (int i = 0; i < n; i++)
            cin >> v[i];
    }

    template<typename T>
    void read(vector<T>& v, int l, int r) {
        assert(0 <= l && l <= r && r < v.size());
        for (int i = l; i <= r; i++)
            cin >> v[i];
    }
}

using namespace input;

// output
namespace output {
    void fileout(const string FILENAME) { freopen(FILENAME.c_str(), "w", stdout); }
    void fileerr(const string FILENAME) { freopen(FILENAME.c_str(), "w", stderr); }

    template<typename T1, typename T2>
    ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
        return os << '(' << p.FF << ", " << p.SS << ')';
    }

    template<typename T>
    ostream& operator<<(ostream& os, const vector<T>& v) {
        os << '[';
        if (v.size()) {
            os << *v.begin();
            for (auto i = ++v.begin(); i != v.end(); i++)
                os << ", " << (*i);
        }
        return os << ']';
    }

    template<typename T>
    ostream& operator<<(ostream& os, const ordered_set<T>& s) {
        os << '[';
        if (s.size()) {
            os << *s.begin();
            for (auto i = ++s.begin(); i != s.end(); i++)
                os << ", " << (*i);
        }
        return os << ']';
    }

    template<typename T>
    ostream& operator<<(ostream& os, const fast_set<T>& s) {
        os << '[';
        if (s.size()) {
            os << *s.begin();
            for (auto i = ++s.begin(); i != s.end(); i++)
                os << ", " << (*i);
        }
        return os << ']';
    }

    template<typename T>
    ostream& operator<<(ostream& os, const multiset<T>& s) {
        os << '[';
        if (s.size()) {
            os << *s.begin();
            for (auto i = ++s.begin(); i != s.end(); i++)
                os << ", " << (*i);
        }
        return os << ']';
    }

    template<typename T1, typename T2>
    ostream& operator<<(ostream& os, const ordered_map<T1, T2>& s) {
        os << '[';
        if (s.size()) {
            os << *s.begin();
            for (auto i = ++s.begin(); i != s.end(); i++)
                os << ", " << (*i);
        }
        return os << ']';
    }

    template<typename T1, typename T2>
    ostream& operator<<(ostream& os, const fast_map<T1, T2>& s) {
        os << '[';
        if (s.size()) {
            os << *s.begin();
            for (auto i = ++s.begin(); i != s.end(); i++)
                os << ", " << (*i);
        }
        return os << ']';
    }

    #define debug(s, x) cerr << __FUNCTION__ << ": " << __LINE__ << ": " << s << " = " << x << '\n';
    #define debug0(x) debug("val", x);
    #define fixfloat(d) fixed << setprecision(d)

    void print() {}

    template<typename T, typename... U> 
    void print(T F, U... S) {
        cout << F;
        print(S...);
    }

    void printl() {}

    template<typename T, typename... U> 
    void printl(T F, U... S) {
        cout << F << '\n';
        printl(S...);
    }

    template<typename T>
    void prints(T F) {
        cout << F;
    }

    template<typename T, typename... U> 
    void prints(T F, U... S) {
        cout << F << ' ';
        prints(S...);
    }

    void printc(string c) {}

    template<typename T, typename... U> 
    void printc(const string c, T F, U... S) {
        cout << F << c;
        printc(c, S...);
    }

    template<typename T>
    void printa(T* a, int n, string s = " ", string e = "\n") {
        for (int i = 0; i < n; i++) 
            cout << a[i] << s;
        cout << e;
    }

    template<typename T>
    void printa(T* a, int l, int r, string s = " ", string e = "\n") {
        for (int i = l; i < r; i++) 
            cout << a[i] << s;
        cout << e;
    }

    template<typename T>
    void printa(vector<T>& v, string s = " ", string e = "\n") {
        for (auto x : v) 
            cout << x << s;
    }

    template<typename T>
    void printa(vector<T>& v, int l, int r, string s = " ", string e = "\n") {
        assert(0 <= l && l <= r && r < v.size());
        for (int i = l; i <= r; i++)
            cout << v[i] << s;
        cout << e;
    }

    template<typename T>
    void printa(ordered_set<T>& v, string s = " ", string e = "\n") {
        for (auto x : v) 
            cout << x << s;
    }

    template<typename T>
    void printa(ordered_set<T>& v, int l, int r, string s = " ", string e = "\n") {
        assert(0 <= l && l <= r && r < v.size());
        auto L = v.find_by_order(l), R = ++v.find_by_order(r);
        for (; L != R; L++)
            cout << *L << s;
        cout << e;
    }

    template<typename T>
    void printa(fast_set<T>& v, string s = " ", string e = "\n") {
        for (auto x : v) 
            cout << x << s;
    }
}

using namespace output;

// code
int N, Q, A[100005], L[400005];
pii T[400005];

inline pii merge(pii a, pii b) {
    return MP(min(a.FF, b.FF), max(a.SS, b.SS));
}

void pushdown(int t, int tl, int tr) {
    if (L[t]) {
        T[t << 1] = MP(T[t << 1].FF + L[t], T[t << 1].SS + L[t]);
        L[t << 1] += L[t];
        T[t << 1 | 1] = MP(T[t << 1 | 1].FF + L[t], T[t << 1 | 1].SS + L[t]);
        L[t << 1 | 1] += L[t];
        L[t] = 0;
    }
}

void init(int* a, int t = 1, int tl = 1, int tr = N) {
    if (tl == tr) {
        T[t] = MP(a[tl], a[tl]);
        return;
    }

    int tm = (tl + tr) >> 1;
    init(a, t << 1, tl, tm);
    init(a, t << 1 | 1, tm + 1, tr);
    T[t] = merge(T[t << 1], T[t << 1 | 1]);
}

void update(int l, int r, int v, int t = 1, int tl = 1, int tr = N) {
    if (r < tl || tr < l || tr < tl) 
        return;
    if (l <= tl && tr <= r) {
        T[t] = MP(T[t].FF + v, T[t].SS + v);
        L[t] += v;
        return;
    }
    if (tl != tr)
        pushdown(t, tl, tr);

    int tm = (tl + tr) >> 1;
    update(l, r, v, t << 1, tl, tm);
    update(l, r, v, t << 1 | 1, tm + 1, tr);
    T[t] = merge(T[t << 1], T[t << 1 | 1]);
}

// returns the element at index u
int query(int u, int t = 1, int tl = 1, int tr = N) {
    if (tl == tr)
        return T[t].FF;
    else 
        pushdown(t, tl, tr);
    
    int tm = (tl + tr) >> 1;
    if (u <= tm)
        return query(u, t << 1, tl, tm);
    else 
        return query(u, t << 1 | 1, tm + 1, tr);
}

// returns the first index with value greater than or equal to v
int query0(int v, int t = 1, int tl = 1, int tr = N) {
    if (tl == tr)
        return tl;
    else 
        pushdown(t, tl, tr);

    int tm = (tl + tr) >> 1;
    if (T[t << 1].SS >= v)
        return query0(v, t << 1, tl, tm);
    if (T[t << 1 | 1].SS >= v)
        return query0(v, t << 1 | 1, tm + 1, tr); 
    return N + 1;
}

// returns last index with value less than or equal to v
int query1(int v, int t = 1, int tl = 1, int tr = N) {
    if (tl == tr)
        return tl;
    else 
        pushdown(t, tl, tr);

    int tm = (tl + tr) >> 1;
    if (T[t << 1 | 1].FF <= v)
        return query1(v, t << 1 | 1, tm + 1, tr);
    if (T[t << 1].FF <= v)
        return query1(v, t << 1, tl, tm);
    return 0;
}

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);

    read(N, Q);
    read(A, 1, N);
    sort(A + 1, A + 1 + N);
    init(A);
    while (Q--) {
        char t; read(t);
        if (t == 'F') {
            int c, h; read(c, h);
            int ul = query0(h), ur = min(ul + c - 1, N); // endpoints of update
            if (ur == N) {
                update(ul, ur, 1);
                continue;
            }
            int e = query(ur);                       // value of last elems in range
            int el = query0(e), er = query1(e);      // endpoints of equal range
            //prints(ul, ur, e, el, er, '\n');
            update(ul, el - 1, 1);
            update(er - (ur - el + 1) + 1, er, 1);
        }
        else if (t == 'C') {
            int l, r; read(l, r);
            printl(query1(r) - query0(l) + 1);
        }
        /*
        else if (t == '0') {
            int u; read(u);
            printl(query0(u));
        }
        else if (t == '1') {
            int u; read(u);
            printl(query1(u));
        }
        else if (t == '2') {
            int u; read(u);
            printl(query(u));
        }
        else if (t == '3') {
            int l, r, v; read(l, r, v);
            update(l, r, v);
        }
        */
    }
}

Compilation message (stderr)

grow.cpp: In function 'void input::filein(std::string)':
grow.cpp:362:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  362 |     void filein(const string FILENAME) { freopen(FILENAME.c_str(), "r", stdin); }
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
grow.cpp: In function 'void output::fileout(std::string)':
grow.cpp:415:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  415 |     void fileout(const string FILENAME) { freopen(FILENAME.c_str(), "w", stdout); }
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
grow.cpp: In function 'void output::fileerr(std::string)':
grow.cpp:416:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  416 |     void fileerr(const string FILENAME) { freopen(FILENAME.c_str(), "w", stderr); }
      |                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10