Submission #331178

#	Time	Username	Problem	Language	Result	Execution time	Memory
331178		Falcon	Matryoshka (JOI16_matryoshka)	C++17	51 / 100	783 ms	262148 KiB

matryoshka

#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; }

template<int n>
class segment_tree {

    struct node {
        int v{};
        node* l{nullptr}; node* r{nullptr};
    };

    using pnode = node*;

    pnode root{nullptr};

private:

    static int value(const pnode& t) {
        return t ? t->v : 0;
    }

    static void pull(const pnode& t) {
        if(t)
            t->v = max(value(t->l), value(t->r));
    }

    void update(pnode& t, int s, int e, int i, int v) {
        if(!t)
            t = new node{};

        if(e <= i || i < s)
            return;

        if(e - s == 1)
            return t->v = v, void();
        
        int m{(s + e) >> 1};
        update(t->l, s, m, i, v); update(t->r, m, e, i, v);
        pull(t);
    }

    int query(const pnode& t, int s, int e, int l, int r) const {
        if(!t || r <= s || e <= l)
            return 0;
        
        if(l <= s && e <= r)
            return value(t);

        int m{(s + e) >> 1};
        return max(query(t->l, s, m, l, r), query(t->r, m, e, l, r));
    }


public:
    
    void update(int i, int v) {
        update(root, 0, n, i, v);
    }

    int query(int l, int r) const {
        return query(root, 0, n, l, r);
    }

};


template<int n, int m>
class segment_tree_2D {

    struct node {
        segment_tree<m> v{};
        node *l{}; node *r{};
    };

    using pnode = node*;

    pnode root{nullptr};

private:

    void update(pnode& t, int s, int e, int i, int j, int v) {
        if(!t)
            t = new node{};
        
        if(i < s || e <= i)
            return;
        
        t->v.update(j, v);

        if(e - s > 1) {
            int mid{(s + e) >> 1};
            update(t->l, s, mid, i, j, v);
            update(t->r, mid, e, i, j, v);
        }
    }

    int query(const pnode& t, int s, int e, int i1, int i2, int j1, int j2) const {
        if(!t || i2 <= s || e <= i1)
            return 0;

        if(i1 <= s && e <= i2)
            return t->v.query(j1, j2);
        
        int mid{(s + e) >> 1};
        return max(query(t->l, s, mid, i1, i2, j1, j2), query(t->r, mid, e, i1, i2, j1, j2));
    }


public:

    void update(int i, int j, int v) {
        update(root, 0, n, i, j, v);
    }

    int query(int i1, int i2, int j1, int j2) const {
        return query(root, 0, n, i1, i2, j1, j2);
    }
    
};

constexpr int MAXV{2'000'000};

segment_tree_2D<MAXV, MAXV> seg;

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

    vector<pair<int, int>> v(N);

    rep(i, N) cin >> v[i].first >> v[i].second, v[i].second = MAXV - v[i].second;

    sort(rall(v));

    struct compress {
        vector<int> values;

        void insert(int x) { values.push_back(x); }

        void apply() { sort(all(values)); values.erase(unique(all(values)), values.end()); }

        int get_rank(int x) { return int(lower_bound(all(values), x) - values.begin()); }
    };

    compress X, Y;

    for(const auto& [x, y] : v) X.insert(x), Y.insert(y);
    X.apply(), Y.apply();

    for(auto& [x, y] : v) {
        x = X.get_rank(x), y = Y.get_rank(y);
        seg.update(x, y, 1 + seg.query(x, MAXV, y, MAXV));
    }

    debug(v);

    rep(i, Q) {
        int A, B; cin >> A >> B; B = MAXV - B;
        A = X.get_rank(A), B = Y.get_rank(B);
        cout << seg.query(A, MAXV, B, MAXV) << '\n';
    }


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

    return 0;
}

Compilation message (stderr)

matryoshka.cpp: In function 'int main()':
matryoshka.cpp:35:29: warning: statement has no effect [-Wunused-value]
   35 | #define debug(x...)         42
      |                             ^~
matryoshka.cpp:205:5: note: in expansion of macro 'debug'
  205 |     debug(v);
      |     ^~~~~

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 0 / 49