Submission #254557

#	Time	Username	Problem	Language	Result	Execution time	Memory
254557		karma	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	2728 ms	104964 KiB

sortbooks

#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair
//#define int         int64_t

using namespace std;

const int N = int(1e6) + 7;
typedef pair<int, int> pii;

int a[N];
pii operator + (const pii& x, const pii& y) {
    if(x.fi <= y.se) return y;
    if(y.fi <= x.se) return x;
    return pii(max(x.fi, y.fi), min(x.fi, y.fi));
}
struct TSegment {
    vector<int> l, h;
    vector<pii> st;
    TSegment() {}
    void init(int n) {
        l.resize(4 * n + 4);
        h.resize(l.size());
        st.resize(l.size());
        build(1, 1, n);
    }
    void build(int x, int low, int high) {
        l[x] = low, h[x] = high, st[x] = pii(0, 0);
        if(l[x] == h[x]) {
            st[x].fi = a[low];
            return;
        }
        int mid = low + high >> 1;
        build(x << 1, low, mid);
        build(x << 1 | 1, mid + 1, high);
    }
    pii get(int x, int low, int high) {
        if(l[x] > high || h[x] < low) return pii(0, 0);
        if(low <= l[x] && h[x] <= high) return st[x];
        return get(x << 1, low, high) + get(x << 1 | 1, low, high);
    }
} it;

int b[N], n, q;

int get(int l, int r) {
    int low = l, high = r, mid;
    while(low <= high) {
        mid = low + high >> 1;
        if(b[r] - b[mid] == r - mid) high = mid - 1;
        else low = mid + 1;
    }
    /// from low to r is non-decreasing
    if(low == l) return 0;
    pii val = it.get(1, l, high);
    high = r;
    while(low <= high) {
        mid = low + high >> 1;
        if(a[mid] < val.fi) low = mid + 1;
        else high = mid - 1;
    }
    /// low to r no change
    val = it.get(1, l, high);
    return val.fi + val.se;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        b[i] = b[i - 1] + (a[i] >= a[i - 1]);
    }
    it.init(n);
    int l, r, k;
    while(q --) {
        cin >> l >> r >> k;
        if(get(l, r) <= k) cout << "1\n";
        else cout << "0\n";
    }
}

Compilation message (stderr)

sortbooks.cpp: In member function 'void TSegment::build(int, int, int)':
sortbooks.cpp:36:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = low + high >> 1;
                   ~~~~^~~~~~
sortbooks.cpp: In function 'int get(int, int)':
sortbooks.cpp:52:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         mid = low + high >> 1;
               ~~~~^~~~~~
sortbooks.cpp:61:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         mid = low + high >> 1;
               ~~~~^~~~~~
sortbooks.cpp: In function 'int32_t main()':
sortbooks.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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