Submission #380439

#	Time	Username	Problem	Language	Result	Execution time	Memory
380439		JerryLiu06	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++11	100 / 100	1678 ms	97100 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

typedef pair<pair<int, int>, int> pii;

#define pb push_back

#define f first
#define s second

int N, M, A[1000010]; vector<pii> Q[1000010]; int tree[4000010], ans[1000010];

void update(int x, int l, int r, int pos, int val) { int mid = (l + r) / 2;
    if (r < pos || l > pos) return ; if (l == r) { tree[x] = val; return ; }

    update(2 * x, l, mid, pos, val); update(2 * x + 1, mid + 1, r, pos, val);

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

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

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

    for (int i = 0; i < M; i++) { int A, B, M; cin >> A >> B >> M; Q[B].pb(pii {{A, M}, i}); }

    stack<int> CUR; for (int i = 1; i <= N; i++) {
        while (!CUR.empty() && A[CUR.top()] <= A[i]) CUR.pop();

        if (!CUR.empty()) update(1, 1, N, CUR.top(), A[CUR.top()] + A[i]); CUR.push(i);

        for (pii X : Q[i]) { ans[X.s] = (query(1, 1, N, X.f.f, N) <= X.f.s); }
    }
    for (int i = 0; i < M; i++) cout << ans[i] << "\n";
}

Compilation message (stderr)

sortbooks.cpp: In function 'void update(int, int, int, int, int)':
sortbooks.cpp:15:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   15 |     if (r < pos || l > pos) return ; if (l == r) { tree[x] = val; return ; }
      |     ^~
sortbooks.cpp:15:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   15 |     if (r < pos || l > pos) return ; if (l == r) { tree[x] = val; return ; }
      |                                      ^~
sortbooks.cpp: In function 'int query(int, int, int, int, int)':
sortbooks.cpp:22:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   22 |     if (r < tl || l > tr) return 0; if (tl <= l && r <= tr) return tree[x];
      |     ^~
sortbooks.cpp:22:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   22 |     if (r < tl || l > tr) return 0; if (tl <= l && r <= tr) return tree[x];
      |                                     ^~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:37:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   37 |         if (!CUR.empty()) update(1, 1, N, CUR.top(), A[CUR.top()] + A[i]); CUR.push(i);
      |         ^~
sortbooks.cpp:37:76: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   37 |         if (!CUR.empty()) update(1, 1, N, CUR.top(), A[CUR.top()] + A[i]); CUR.push(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