Submission #380350

#	Time	Username	Problem	Language	Result	Execution time	Memory
380350		JerryLiu06	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++11	0 / 100	3094 ms	262144 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

struct Node { int max, maxInv; vector<int> nums; } tree[4000010];

int N, M, A[1000010]; const int INF = 2000000010;

Node comb(Node A, Node B) { Node res;
    merge(A.nums.begin(), A.nums.end(), B.nums.begin(), B.nums.end(), back_inserter(res.nums));
    
    res.max = max(A.max, B.max);

    int L = A.max; int pos = lower_bound(B.nums.begin(), B.nums.end(), L) - B.nums.begin() - 1;

    if (pos == -1) { res.maxInv = max(A.maxInv, B.maxInv); return res; }

    int nInv = L + res.nums[pos]; res.maxInv = max(max(A.maxInv, B.maxInv), nInv); return res;
}
void build(int x, int l, int r) { int mid = (l + r) / 2;
    if (l == r) { tree[x].max = A[l]; tree[x].nums = vector<int>(1, A[l]); return ; }

    build(2 * x, l, mid); build(2 * x + 1, mid + 1, r); tree[x] = comb(tree[2 * x], tree[2 * x + 1]);
}
Node query(int x, int l, int r, int tl, int tr) { int mid = (l + r) / 2;
    if (r < tl || l > tr) return Node{0, 0, vector<int>(0)}; if (tl <= l && r <= tr) return tree[x];

    return comb(query(2 * x, l, mid, tl, tr), query(2 * x + 1, mid + 1, r, tl, tr));
}

int main() {
    cin >> N >> M; for (int i = 1; i <= N; i++) cin >> A[i];

    build(1, 1, N); for (int i = 0; i < M; i++) { int A, B, M; cin >> A >> B >> M;

        Node CUR = query(1, 1, N, A, B); cout << (CUR.maxInv <= M) << "\n";
    }
}

Compilation message (stderr)

sortbooks.cpp: In function 'Node query(int, int, int, int, int)':
sortbooks.cpp:26:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   26 |     if (r < tl || l > tr) return Node{0, 0, vector<int>(0)}; if (tl <= l && r <= tr) return tree[x];
      |     ^~
sortbooks.cpp:26:62: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   26 |     if (r < tl || l > tr) return Node{0, 0, vector<int>(0)}; if (tl <= l && r <= tr) return tree[x];
      |                                                              ^~

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