Submission #331118

#	Time	Username	Problem	Language	Result	Execution time	Memory
331118		Falcon	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	2519 ms	119496 KiB

sortbooks

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



namespace segtree {

struct node {
    int max_a{}, v{}, lzy{-1};
};

vector<node> seg;

void push(int n, int s, int e) {
    if(seg[n].lzy == -1)
        return;

    seg[n].v = seg[n].max_a + seg[n].lzy;
    
    if(s != e)
        seg[n << 1].lzy = seg[n << 1 | 1].lzy = seg[n].lzy;
    
    seg[n].lzy = -1;
}

void update(int n, int s, int e, int l, int r, int v) {
    push(n, s, e);
    if(r < s || e < l)
        return;

    if(l <= s && e <= r) {
        seg[n].lzy = v;
        push(n, s, e);
        return;
    }

    int m{(s + e) >> 1};
    update(n << 1, s, m, l, r, v); update(n << 1 | 1, m + 1, e, l, r, v);
    seg[n].v = max(seg[n << 1].v, seg[n << 1 | 1].v);
}

void add_front(int n, int s, int e, int i, int v) {
    push(n, s, e);
    if(e < i || i < s)
        return;

    if(s == e) {
        assert(seg[n].max_a == 0 && seg[n].v == 0);
        seg[n].max_a = v;
        return;        
    }

    int m{(s + e) >> 1};
    add_front(n << 1, s, m, i, v), add_front(n << 1 | 1, m + 1, e, i, v);
    seg[n].v = max(seg[n << 1].v, seg[n << 1 | 1].v);
    seg[n].max_a = max(seg[n << 1].max_a, seg[n << 1 | 1].max_a);
}

int query(int n, int s, int e, int l, int r) {
    push(n, s, e);
    if(r < s || e < l)
        return 0;

    if(l <= s && e <= r)
        return seg[n].v;

    int m{(s + e) >> 1};
    return max(query(n << 1, s, m, l, r), query(n << 1 | 1, m + 1, e, l, r));
}

} // namespace segtree


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    #ifdef DEBUG
    freopen("debug", "w", stderr);
    #endif
    
    int N, M; cin >> N >> M;
    vector<int> A(N); segtree::seg.resize(N << 2);
    rep(i, N) cin >> A[i];

    struct query { int i, r, k; };

    vector<vector<query>> queries(N);
    vector<bool> ans(M);
    rep(i, M) {
        int l, r, k; cin >> l >> r >> k; --l, --r;
        queries[l].push_back({i, r, k});
    }
    
    A.push_back(*max_element(all(A)) + 1);
    stack<int> max_vals; max_vals.push(N);
    rrep(i, N) {
        while(!max_vals.empty() && A[max_vals.top()] < A[i])
            max_vals.pop();
        int e = max_vals.top() - 1;
        debug(i, e);
        if(e > i) segtree::update(1, 0, N - 1, i + 1, e, A[i]);
        for(const query& q : queries[i]) {
            int x{segtree::query(1, 0, N - 1, i, q.r)};
            debug(x, q.i);
            ans[q.i] = x <= q.k;

        }
        segtree::add_front(1, 0, N - 1, i, A[i]);
        max_vals.push(i);
    }

    for(const auto& b : ans) cout << b << '\n';

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

    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:35:29: warning: statement has no effect [-Wunused-value]
   35 | #define debug(x...)         42
      |                             ^~
sortbooks.cpp:145:9: note: in expansion of macro 'debug'
  145 |         debug(i, e);
      |         ^~~~~
sortbooks.cpp:35:29: warning: statement has no effect [-Wunused-value]
   35 | #define debug(x...)         42
      |                             ^~
sortbooks.cpp:149:13: note: in expansion of macro 'debug'
  149 |             debug(x, q.i);
      |             ^~~~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23