Submission #1109776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109776		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1204 ms	90748 KiB

sortbooks

#include <bits/stdc++.h>
#define task "HUUNGHI"
#define task2 "A"
#define pl pair<ll, ll>
#define pf push_front
#define pb push_back
#define pob pop_back
#define pof pop_front
#define mp make_pair
#define fi first
#define se second
#define FOR(i, a, b, c) for (ull i=a; i<=b; i+=c)
#define FORE(i, a, b, c) for (ull i=a; i>=b; i+=c)
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int Mod = 1e9+7;
const int maxn = 1e6;
const ll Inf = 3e9;
ll A[maxn+1], F[maxn+1], id = 1;
ll n, m, res[maxn+1];
struct Query {
    ll l, r, k, pos;
};
Query Q[maxn+1];
stack<ll> B;
ll Get(ll pos) {
    ll res = -Inf;
    while (pos <= n) {
        res = max(res, F[pos]);
        pos += (pos & -pos);
    }
    return res;
}
void Update(ll pos, ll v)
{
    while (pos > 0) {
        F[pos] = max(F[pos], v);
        pos -= (pos & -pos);
    }
}
void Read()
{
    memset(F, -0x3f, sizeof(F));
    cin >> n >> m;
    FOR(i, 1, n, 1) cin >> A[i];
    FOR(i, 1, m, 1) {
        cin >> Q[i].l >> Q[i].r >> Q[i].k;
        Q[i].pos = i;
    }
}
void Solve()
{
    sort (Q + 1, Q + m + 1, [&] (Query a, Query b) {
        return a.r < b.r;
    });
    FOR(i, 1, m, 1) {
        while (id <= Q[i].r) {
            while (B.size() and A[B.top()] <= A[id]) B.pop();
            if (B.size()) Update(B.top(), A[B.top()] + A[id]);
            B.push(id++);
        }
        res[Q[i].pos] = (Get(Q[i].l) <= Q[i].k);
    }
    FOR(i, 1, m, 1) cout << res[i] << '\n';
}
int main()
{
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    //ios_base::sync_with_stdio(0);
    //cin.tie(0); cout.tie(0);
    int t;
    for (t=1; t--;)
    {
        Read(); Solve();
    }
}

Compilation message (stderr)

sortbooks.cpp: In function 'void Read()':
sortbooks.cpp:12:40: warning: comparison of integer expressions of different signedness: 'ull' {aka 'long long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   12 | #define FOR(i, a, b, c) for (ull i=a; i<=b; i+=c)
......
   46 |     FOR(i, 1, n, 1) cin >> A[i];
      |         ~~~~~~~                         
sortbooks.cpp:46:5: note: in expansion of macro 'FOR'
   46 |     FOR(i, 1, n, 1) cin >> A[i];
      |     ^~~
sortbooks.cpp:12:40: warning: comparison of integer expressions of different signedness: 'ull' {aka 'long long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   12 | #define FOR(i, a, b, c) for (ull i=a; i<=b; i+=c)
......
   47 |     FOR(i, 1, m, 1) {
      |         ~~~~~~~                         
sortbooks.cpp:47:5: note: in expansion of macro 'FOR'
   47 |     FOR(i, 1, m, 1) {
      |     ^~~
sortbooks.cpp: In function 'void Solve()':
sortbooks.cpp:12:40: warning: comparison of integer expressions of different signedness: 'ull' {aka 'long long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   12 | #define FOR(i, a, b, c) for (ull i=a; i<=b; i+=c)
......
   57 |     FOR(i, 1, m, 1) {
      |         ~~~~~~~                         
sortbooks.cpp:57:5: note: in expansion of macro 'FOR'
   57 |     FOR(i, 1, m, 1) {
      |     ^~~
sortbooks.cpp:12:40: warning: comparison of integer expressions of different signedness: 'ull' {aka 'long long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   12 | #define FOR(i, a, b, c) for (ull i=a; i<=b; i+=c)
......
   65 |     FOR(i, 1, m, 1) cout << res[i] << '\n';
      |         ~~~~~~~                         
sortbooks.cpp:65:5: note: in expansion of macro 'FOR'
   65 |     FOR(i, 1, m, 1) cout << res[i] << '\n';
      |     ^~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:70:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:71:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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