oj.uz

Submission #255259

# Submission time Handle Problem Language Result Execution time Memory
255259 2020-07-31T16:35:02 Z karma Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 2025 ms 113364 KB 
#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair
//#define int         int64_t

using namespace std;

const int N = int(1e6) + 7;
const int M = N << 2;
const int inf = 2e9 + 1;
typedef pair<int, int> pii;

int l[M], h[M], st[M];
int a[N], n, m, ans[N];
vector<pair<int, pii>> ask[N];

void build(int x, int low, int high) {
    l[x] = low, h[x] = high;
    if(l[x] == h[x]) return;
    int mid = (low + high) >> 1;
    build(x << 1, low, mid);
    build(x << 1 | 1, mid + 1, high);
}

void upd(int x, int pos, int val) {
    if(l[x] > pos || h[x] < pos) return;
    if(l[x] == h[x]) {
        st[x] = max(st[x], val);
        return;
    }
    upd(x << 1, pos, val);
    upd(x << 1 | 1, pos, val);
    st[x] = max(st[x << 1], st[x << 1 | 1]);
}

int get(int x, int low, int high) {
    if(l[x] > high || h[x] < low) return 0;
    if(l[x] >= low && h[x] <= high) return st[x];
    return max(get(x << 1, low, high), get(x << 1 | 1, low, high));
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int u, v, w, i = 1; i <= m; ++i) {
        cin >> u >> v >> w;
        ask[v].pb(i, pii(u, w));
    }
    build(1, 1, n);
    vector<int> st;
    for(int i = 1; i <= n; ++i) {
        while(st.size() && a[st.back()] <= a[i]) st.pop_back();
        if(st.size()) {
            upd(1, st.back(), a[st.back()] + a[i]);
        }
        st.pb(i);
        for(auto q: ask[i]) {
            //cout << q.fi << ' ' << get(1, q.se.fi, i) << '\n';
            ans[q.fi] = get(1, q.se.fi, i) <= q.se.se;
        }
    }
    for(int i = 1; i <= m; ++i) cout << ans[i] << '\n';
}

Compilation message

sortbooks.cpp: In function 'int32_t main()':
sortbooks.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 15 ms 23936 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 15 ms 23936 KB Output is correct
6 Correct 20 ms 23936 KB Output is correct
7 Correct 15 ms 23936 KB Output is correct
8 Correct 15 ms 23936 KB Output is correct
9 Correct 15 ms 23936 KB Output is correct
10 Correct 15 ms 23936 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 15 ms 23936 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 15 ms 23936 KB Output is correct
6 Correct 20 ms 23936 KB Output is correct
7 Correct 15 ms 23936 KB Output is correct
8 Correct 15 ms 23936 KB Output is correct
9 Correct 15 ms 23936 KB Output is correct
10 Correct 15 ms 23936 KB Output is correct
11 Correct 19 ms 24064 KB Output is correct
12 Correct 18 ms 24224 KB Output is correct
13 Correct 26 ms 24320 KB Output is correct
14 Correct 20 ms 24320 KB Output is correct
15 Correct 21 ms 24320 KB Output is correct
16 Correct 19 ms 24320 KB Output is correct
17 Correct 19 ms 24192 KB Output is correct
18 Correct 23 ms 24192 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1849 ms 80472 KB Output is correct
2 Correct 1812 ms 112888 KB Output is correct
3 Correct 1816 ms 112760 KB Output is correct
4 Correct 1837 ms 112996 KB Output is correct
5 Correct 1553 ms 104816 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 30968 KB Output is correct
2 Correct 117 ms 30712 KB Output is correct
3 Correct 117 ms 29828 KB Output is correct
4 Correct 110 ms 29816 KB Output is correct
5 Correct 109 ms 29944 KB Output is correct
6 Correct 90 ms 29432 KB Output is correct
7 Correct 90 ms 29432 KB Output is correct
8 Correct 103 ms 29744 KB Output is correct
9 Correct 57 ms 26800 KB Output is correct
10 Correct 103 ms 29744 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 15 ms 23936 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 15 ms 23936 KB Output is correct
6 Correct 20 ms 23936 KB Output is correct
7 Correct 15 ms 23936 KB Output is correct
8 Correct 15 ms 23936 KB Output is correct
9 Correct 15 ms 23936 KB Output is correct
10 Correct 15 ms 23936 KB Output is correct
11 Correct 19 ms 24064 KB Output is correct
12 Correct 18 ms 24224 KB Output is correct
13 Correct 26 ms 24320 KB Output is correct
14 Correct 20 ms 24320 KB Output is correct
15 Correct 21 ms 24320 KB Output is correct
16 Correct 19 ms 24320 KB Output is correct
17 Correct 19 ms 24192 KB Output is correct
18 Correct 23 ms 24192 KB Output is correct
19 Correct 290 ms 37112 KB Output is correct
20 Correct 295 ms 37184 KB Output is correct
21 Correct 257 ms 36728 KB Output is correct
22 Correct 261 ms 36604 KB Output is correct
23 Correct 260 ms 36600 KB Output is correct
24 Correct 213 ms 34424 KB Output is correct
25 Correct 214 ms 34552 KB Output is correct
26 Correct 231 ms 34740 KB Output is correct
27 Correct 241 ms 34680 KB Output is correct
28 Correct 235 ms 34808 KB Output is correct
29 Correct 297 ms 35192 KB Output is correct
30 Correct 249 ms 35104 KB Output is correct
31 Correct 248 ms 35064 KB Output is correct
32 Correct 265 ms 35336 KB Output is correct
33 Correct 272 ms 35192 KB Output is correct
34 Correct 200 ms 34152 KB Output is correct
35 Correct 188 ms 34168 KB Output is correct
36 Correct 207 ms 34168 KB Output is correct
37 Correct 185 ms 34168 KB Output is correct
38 Correct 199 ms 34296 KB Output is correct
39 Correct 236 ms 35376 KB Output is correct
40 Correct 202 ms 32040 KB Output is correct
41 Correct 247 ms 34732 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 15 ms 23936 KB Output is correct
4 Correct 15 ms 23936 KB Output is correct
5 Correct 15 ms 23936 KB Output is correct
6 Correct 20 ms 23936 KB Output is correct
7 Correct 15 ms 23936 KB Output is correct
8 Correct 15 ms 23936 KB Output is correct
9 Correct 15 ms 23936 KB Output is correct
10 Correct 15 ms 23936 KB Output is correct
11 Correct 19 ms 24064 KB Output is correct
12 Correct 18 ms 24224 KB Output is correct
13 Correct 26 ms 24320 KB Output is correct
14 Correct 20 ms 24320 KB Output is correct
15 Correct 21 ms 24320 KB Output is correct
16 Correct 19 ms 24320 KB Output is correct
17 Correct 19 ms 24192 KB Output is correct
18 Correct 23 ms 24192 KB Output is correct
19 Correct 1849 ms 80472 KB Output is correct
20 Correct 1812 ms 112888 KB Output is correct
21 Correct 1816 ms 112760 KB Output is correct
22 Correct 1837 ms 112996 KB Output is correct
23 Correct 1553 ms 104816 KB Output is correct
24 Correct 128 ms 30968 KB Output is correct
25 Correct 117 ms 30712 KB Output is correct
26 Correct 117 ms 29828 KB Output is correct
27 Correct 110 ms 29816 KB Output is correct
28 Correct 109 ms 29944 KB Output is correct
29 Correct 90 ms 29432 KB Output is correct
30 Correct 90 ms 29432 KB Output is correct
31 Correct 103 ms 29744 KB Output is correct
32 Correct 57 ms 26800 KB Output is correct
33 Correct 103 ms 29744 KB Output is correct
34 Correct 290 ms 37112 KB Output is correct
35 Correct 295 ms 37184 KB Output is correct
36 Correct 257 ms 36728 KB Output is correct
37 Correct 261 ms 36604 KB Output is correct
38 Correct 260 ms 36600 KB Output is correct
39 Correct 213 ms 34424 KB Output is correct
40 Correct 214 ms 34552 KB Output is correct
41 Correct 231 ms 34740 KB Output is correct
42 Correct 241 ms 34680 KB Output is correct
43 Correct 235 ms 34808 KB Output is correct
44 Correct 297 ms 35192 KB Output is correct
45 Correct 249 ms 35104 KB Output is correct
46 Correct 248 ms 35064 KB Output is correct
47 Correct 265 ms 35336 KB Output is correct
48 Correct 272 ms 35192 KB Output is correct
49 Correct 200 ms 34152 KB Output is correct
50 Correct 188 ms 34168 KB Output is correct
51 Correct 207 ms 34168 KB Output is correct
52 Correct 185 ms 34168 KB Output is correct
53 Correct 199 ms 34296 KB Output is correct
54 Correct 236 ms 35376 KB Output is correct
55 Correct 202 ms 32040 KB Output is correct
56 Correct 247 ms 34732 KB Output is correct
57 Correct 1949 ms 113364 KB Output is correct
58 Correct 2025 ms 113112 KB Output is correct
59 Correct 1769 ms 111564 KB Output is correct
60 Correct 1710 ms 111508 KB Output is correct
61 Correct 1766 ms 111644 KB Output is correct
62 Correct 1797 ms 111732 KB Output is correct
63 Correct 1062 ms 99812 KB Output is correct
64 Correct 1121 ms 99464 KB Output is correct
65 Correct 1457 ms 103264 KB Output is correct
66 Correct 1467 ms 103340 KB Output is correct
67 Correct 1566 ms 103388 KB Output is correct
68 Correct 1609 ms 104884 KB Output is correct
69 Correct 1566 ms 104804 KB Output is correct
70 Correct 1563 ms 104760 KB Output is correct
71 Correct 1519 ms 104844 KB Output is correct
72 Correct 1594 ms 104536 KB Output is correct
73 Correct 965 ms 95732 KB Output is correct
74 Correct 1032 ms 97024 KB Output is correct
75 Correct 984 ms 95896 KB Output is correct
76 Correct 959 ms 96316 KB Output is correct
77 Correct 924 ms 95952 KB Output is correct
78 Correct 1326 ms 99764 KB Output is correct
79 Correct 980 ms 80108 KB Output is correct
80 Correct 1399 ms 94364 KB Output is correct