Submission #889668

#	Time	Username	Problem	Language	Result	Execution time	Memory
889668		chanhchuong123	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1050 ms	96820 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}

const int MAX = 1000010;
int nArr;
int nQuery;
int arr[MAX];
int ans[MAX];
stack<int> s;
int st[(1 << 21) + 5];
vector<tuple<int, int, int>> queries[MAX];

void init(void) {
    cin >> nArr >> nQuery;
    for (int i = 1; i <= nArr; ++i) {
        cin >> arr[i];
    }
    for (int i = 1; i <= nQuery; ++i) {
        int l, r, k; cin >> l >> r >> k;
        queries[r].emplace_back(l, k, i);
    }
}

void update(int pos, int value) {
    int id = 1, l = 1, r = nArr;
    while (l < r) {
        int mid = l + r >> 1;
        if (pos <= mid) id <<= 1, r = mid;
        else id = id << 1 | 1, l = mid + 1;
    }
    st[id] = max(st[id], value);
    while (id > 1) {
        id >>= 1;
        st[id] = max(st[id << 1], st[id << 1 | 1]);
    }
}

int get(int id, int l, int r, int u, int v) {
    if (l > v || r < u) return 0;
    if (l >= u && r <= v) return st[id];
    int mid = l + r >> 1; return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
#define get(l, r) (get(1, 1, nArr, l, r))

void process(void) {
    for (int i = 1; i <= nArr; ++i) {
        while (s.size() && arr[s.top()] <= arr[i])   s.pop();
        if (s.size()) update(s.top(), arr[s.top()] + arr[i]);
        s.push(i);
        for (tuple<int, int, int> &qry: queries[i]) {
            int j, k, id; tie(j, k, id) = qry;
            ans[id] = get(j, i) <= k;
        }
    }
    for (int i = 1; i <= nQuery; ++i) {
        cout << ans[i] << '\n';
    }
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
//	freopen("C.INP", "r",  stdin);
//	freopen("C.OUT", "w", stdout);

    init();
    process();

	return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'void update(int, int)':
sortbooks.cpp:36:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         int mid = l + r >> 1;
      |                   ~~^~~
sortbooks.cpp: In function 'int get(int, int, int, int, int)':
sortbooks.cpp:50:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     int mid = l + r >> 1; return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
      |               ~~^~~

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