oj.uz

Submission #1109776

# Submission time Handle Problem Language Result Execution time Memory
1109776 2024-11-07T14:46:13 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 1204 ms 90748 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12624 KB Output is correct
2 Correct 2 ms 12624 KB Output is correct
3 Correct 2 ms 12624 KB Output is correct
4 Correct 3 ms 12764 KB Output is correct
5 Correct 2 ms 12624 KB Output is correct
6 Correct 2 ms 12624 KB Output is correct
7 Correct 3 ms 12624 KB Output is correct
8 Correct 3 ms 12624 KB Output is correct
9 Correct 2 ms 12624 KB Output is correct
10 Correct 3 ms 12624 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12624 KB Output is correct
2 Correct 2 ms 12624 KB Output is correct
3 Correct 2 ms 12624 KB Output is correct
4 Correct 3 ms 12764 KB Output is correct
5 Correct 2 ms 12624 KB Output is correct
6 Correct 2 ms 12624 KB Output is correct
7 Correct 3 ms 12624 KB Output is correct
8 Correct 3 ms 12624 KB Output is correct
9 Correct 2 ms 12624 KB Output is correct
10 Correct 3 ms 12624 KB Output is correct
11 Correct 5 ms 12880 KB Output is correct
12 Correct 5 ms 12848 KB Output is correct
13 Correct 7 ms 13048 KB Output is correct
14 Correct 8 ms 12988 KB Output is correct
15 Correct 8 ms 12880 KB Output is correct
16 Correct 7 ms 12880 KB Output is correct
17 Correct 6 ms 12940 KB Output is correct
18 Correct 6 ms 12880 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1134 ms 89012 KB Output is correct
2 Correct 1204 ms 89960 KB Output is correct
3 Correct 1097 ms 89720 KB Output is correct
4 Correct 1092 ms 89988 KB Output is correct
5 Correct 1067 ms 89904 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 21064 KB Output is correct
2 Correct 72 ms 21096 KB Output is correct
3 Correct 79 ms 21068 KB Output is correct
4 Correct 74 ms 21100 KB Output is correct
5 Correct 79 ms 21064 KB Output is correct
6 Correct 73 ms 21064 KB Output is correct
7 Correct 72 ms 21108 KB Output is correct
8 Correct 71 ms 20808 KB Output is correct
9 Correct 56 ms 18504 KB Output is correct
10 Correct 69 ms 20812 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12624 KB Output is correct
2 Correct 2 ms 12624 KB Output is correct
3 Correct 2 ms 12624 KB Output is correct
4 Correct 3 ms 12764 KB Output is correct
5 Correct 2 ms 12624 KB Output is correct
6 Correct 2 ms 12624 KB Output is correct
7 Correct 3 ms 12624 KB Output is correct
8 Correct 3 ms 12624 KB Output is correct
9 Correct 2 ms 12624 KB Output is correct
10 Correct 3 ms 12624 KB Output is correct
11 Correct 5 ms 12880 KB Output is correct
12 Correct 5 ms 12848 KB Output is correct
13 Correct 7 ms 13048 KB Output is correct
14 Correct 8 ms 12988 KB Output is correct
15 Correct 8 ms 12880 KB Output is correct
16 Correct 7 ms 12880 KB Output is correct
17 Correct 6 ms 12940 KB Output is correct
18 Correct 6 ms 12880 KB Output is correct
19 Correct 214 ms 27976 KB Output is correct
20 Correct 219 ms 27976 KB Output is correct
21 Correct 205 ms 27728 KB Output is correct
22 Correct 212 ms 27696 KB Output is correct
23 Correct 251 ms 27700 KB Output is correct
24 Correct 206 ms 27720 KB Output is correct
25 Correct 208 ms 27704 KB Output is correct
26 Correct 217 ms 27964 KB Output is correct
27 Correct 215 ms 27836 KB Output is correct
28 Correct 223 ms 27976 KB Output is correct
29 Correct 214 ms 27980 KB Output is correct
30 Correct 232 ms 27976 KB Output is correct
31 Correct 217 ms 27976 KB Output is correct
32 Correct 220 ms 27976 KB Output is correct
33 Correct 216 ms 27964 KB Output is correct
34 Correct 190 ms 27720 KB Output is correct
35 Correct 202 ms 27720 KB Output is correct
36 Correct 203 ms 27464 KB Output is correct
37 Correct 192 ms 27464 KB Output is correct
38 Correct 205 ms 27720 KB Output is correct
39 Correct 180 ms 26444 KB Output is correct
40 Correct 163 ms 25928 KB Output is correct
41 Correct 194 ms 26368 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12624 KB Output is correct
2 Correct 2 ms 12624 KB Output is correct
3 Correct 2 ms 12624 KB Output is correct
4 Correct 3 ms 12764 KB Output is correct
5 Correct 2 ms 12624 KB Output is correct
6 Correct 2 ms 12624 KB Output is correct
7 Correct 3 ms 12624 KB Output is correct
8 Correct 3 ms 12624 KB Output is correct
9 Correct 2 ms 12624 KB Output is correct
10 Correct 3 ms 12624 KB Output is correct
11 Correct 5 ms 12880 KB Output is correct
12 Correct 5 ms 12848 KB Output is correct
13 Correct 7 ms 13048 KB Output is correct
14 Correct 8 ms 12988 KB Output is correct
15 Correct 8 ms 12880 KB Output is correct
16 Correct 7 ms 12880 KB Output is correct
17 Correct 6 ms 12940 KB Output is correct
18 Correct 6 ms 12880 KB Output is correct
19 Correct 1134 ms 89012 KB Output is correct
20 Correct 1204 ms 89960 KB Output is correct
21 Correct 1097 ms 89720 KB Output is correct
22 Correct 1092 ms 89988 KB Output is correct
23 Correct 1067 ms 89904 KB Output is correct
24 Correct 77 ms 21064 KB Output is correct
25 Correct 72 ms 21096 KB Output is correct
26 Correct 79 ms 21068 KB Output is correct
27 Correct 74 ms 21100 KB Output is correct
28 Correct 79 ms 21064 KB Output is correct
29 Correct 73 ms 21064 KB Output is correct
30 Correct 72 ms 21108 KB Output is correct
31 Correct 71 ms 20808 KB Output is correct
32 Correct 56 ms 18504 KB Output is correct
33 Correct 69 ms 20812 KB Output is correct
34 Correct 214 ms 27976 KB Output is correct
35 Correct 219 ms 27976 KB Output is correct
36 Correct 205 ms 27728 KB Output is correct
37 Correct 212 ms 27696 KB Output is correct
38 Correct 251 ms 27700 KB Output is correct
39 Correct 206 ms 27720 KB Output is correct
40 Correct 208 ms 27704 KB Output is correct
41 Correct 217 ms 27964 KB Output is correct
42 Correct 215 ms 27836 KB Output is correct
43 Correct 223 ms 27976 KB Output is correct
44 Correct 214 ms 27980 KB Output is correct
45 Correct 232 ms 27976 KB Output is correct
46 Correct 217 ms 27976 KB Output is correct
47 Correct 220 ms 27976 KB Output is correct
48 Correct 216 ms 27964 KB Output is correct
49 Correct 190 ms 27720 KB Output is correct
50 Correct 202 ms 27720 KB Output is correct
51 Correct 203 ms 27464 KB Output is correct
52 Correct 192 ms 27464 KB Output is correct
53 Correct 205 ms 27720 KB Output is correct
54 Correct 180 ms 26444 KB Output is correct
55 Correct 163 ms 25928 KB Output is correct
56 Correct 194 ms 26368 KB Output is correct
57 Correct 1143 ms 90696 KB Output is correct
58 Correct 1135 ms 90592 KB Output is correct
59 Correct 1113 ms 90444 KB Output is correct
60 Correct 1175 ms 90600 KB Output is correct
61 Correct 1144 ms 90440 KB Output is correct
62 Correct 1109 ms 90420 KB Output is correct
63 Correct 1037 ms 88720 KB Output is correct
64 Correct 1051 ms 88640 KB Output is correct
65 Correct 1061 ms 90516 KB Output is correct
66 Correct 1089 ms 90560 KB Output is correct
67 Correct 1041 ms 90696 KB Output is correct
68 Correct 1022 ms 90640 KB Output is correct
69 Correct 1085 ms 90696 KB Output is correct
70 Correct 1075 ms 90556 KB Output is correct
71 Correct 1066 ms 90684 KB Output is correct
72 Correct 1086 ms 90748 KB Output is correct
73 Correct 997 ms 87100 KB Output is correct
74 Correct 991 ms 88136 KB Output is correct
75 Correct 996 ms 87112 KB Output is correct
76 Correct 1022 ms 87112 KB Output is correct
77 Correct 990 ms 87132 KB Output is correct
78 Correct 980 ms 84436 KB Output is correct
79 Correct 862 ms 76360 KB Output is correct
80 Correct 909 ms 81600 KB Output is correct