oj.uz

Submission #166351

# Submission time Handle Problem Language Result Execution time Memory
166351 2019-12-01T18:23:14 Z koste4ka Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 110264 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

#define pb push_back
#define F first
#define S second
#define lll unsigned long long
#define lld long double

#define data sdadsd

//#define int lll

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree <T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

const int N = 1e6 + 229;
const lll M = 1e9 + 7;
const lll M2 = 1e9 + 9;
const lll mod = 998244353;
const int rx[4] = {0, 0, -1, 1};
const int ry[4] = {-1, 1, 0, 0};
const lld eps = 1e-11;
const double pi = acos(-1.0);

int ans[N];

set < int > all[N];

int a[N];

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(time(0));
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("maxxor.in", "r", stdin);
//    freopen("maxxor.out", "w", stdout);
#endif
    int block = 2000;
    int n, m;
    cin >> n >> m;
    int ind;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        ind = i / block;
        if (!all[ind].empty() && a[i] < *all[ind].rbegin()) {
            ans[ind] = max(ans[ind], a[i] + *all[ind].rbegin());
        }
        all[ind].insert(a[i]);
    }
    int l, r, k;
    int res;
    int best;
    while (m--) {
        cin >> l >> r >> k;
        --l;
        --r;
        res = 0;
        best = 0;
        for (int i = l; i <= r;) {
            if (i % block == 0 && i + block - 1 <= r) {
                res = max(res, ans[i / block]);
                if (best > *all[i / block].begin()) {
                    auto it = all[i / block].lower_bound(best);
                    --it;
                    res = max(res, best + *it);
                }
                best = max(best, *all[i / block].rbegin());
                i += block;
            } else {
                if (best > a[i]) {
                    res = max(res, best + a[i]);
                }
                best = max(best, a[i]);
                ++i;
            }
        }
        cout << (res <= k) << '\n';
    }
    return 0;
}

Compilation message

sortbooks.cpp:45:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47608 KB Output is correct
2 Correct 48 ms 47352 KB Output is correct
3 Correct 47 ms 47324 KB Output is correct
4 Correct 47 ms 47352 KB Output is correct
5 Correct 51 ms 47352 KB Output is correct
6 Correct 46 ms 47352 KB Output is correct
7 Correct 47 ms 47352 KB Output is correct
8 Correct 47 ms 47352 KB Output is correct
9 Correct 47 ms 47352 KB Output is correct
10 Correct 48 ms 47352 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47608 KB Output is correct
2 Correct 48 ms 47352 KB Output is correct
3 Correct 47 ms 47324 KB Output is correct
4 Correct 47 ms 47352 KB Output is correct
5 Correct 51 ms 47352 KB Output is correct
6 Correct 46 ms 47352 KB Output is correct
7 Correct 47 ms 47352 KB Output is correct
8 Correct 47 ms 47352 KB Output is correct
9 Correct 47 ms 47352 KB Output is correct
10 Correct 48 ms 47352 KB Output is correct
11 Correct 52 ms 47480 KB Output is correct
12 Correct 58 ms 47656 KB Output is correct
13 Correct 59 ms 47764 KB Output is correct
14 Correct 65 ms 47736 KB Output is correct
15 Correct 65 ms 47820 KB Output is correct
16 Correct 69 ms 47864 KB Output is correct
17 Correct 57 ms 47608 KB Output is correct
18 Correct 66 ms 47480 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3027 ms 110264 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 51940 KB Output is correct
2 Correct 764 ms 52060 KB Output is correct
3 Correct 575 ms 50092 KB Output is correct
4 Correct 600 ms 49952 KB Output is correct
5 Correct 537 ms 50060 KB Output is correct
6 Correct 807 ms 49920 KB Output is correct
7 Correct 798 ms 49960 KB Output is correct
8 Correct 411 ms 49804 KB Output is correct
9 Correct 159 ms 48928 KB Output is correct
10 Correct 412 ms 49712 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47608 KB Output is correct
2 Correct 48 ms 47352 KB Output is correct
3 Correct 47 ms 47324 KB Output is correct
4 Correct 47 ms 47352 KB Output is correct
5 Correct 51 ms 47352 KB Output is correct
6 Correct 46 ms 47352 KB Output is correct
7 Correct 47 ms 47352 KB Output is correct
8 Correct 47 ms 47352 KB Output is correct
9 Correct 47 ms 47352 KB Output is correct
10 Correct 48 ms 47352 KB Output is correct
11 Correct 52 ms 47480 KB Output is correct
12 Correct 58 ms 47656 KB Output is correct
13 Correct 59 ms 47764 KB Output is correct
14 Correct 65 ms 47736 KB Output is correct
15 Correct 65 ms 47820 KB Output is correct
16 Correct 69 ms 47864 KB Output is correct
17 Correct 57 ms 47608 KB Output is correct
18 Correct 66 ms 47480 KB Output is correct
19 Correct 1468 ms 64676 KB Output is correct
20 Correct 1425 ms 64792 KB Output is correct
21 Correct 2329 ms 64644 KB Output is correct
22 Correct 2353 ms 64572 KB Output is correct
23 Correct 2438 ms 64632 KB Output is correct
24 Correct 1295 ms 64592 KB Output is correct
25 Correct 1313 ms 64504 KB Output is correct
26 Correct 1217 ms 64540 KB Output is correct
27 Correct 1215 ms 64520 KB Output is correct
28 Correct 1258 ms 64664 KB Output is correct
29 Correct 1124 ms 64596 KB Output is correct
30 Correct 1578 ms 64752 KB Output is correct
31 Correct 1180 ms 64728 KB Output is correct
32 Correct 1155 ms 64772 KB Output is correct
33 Correct 1199 ms 64660 KB Output is correct
34 Correct 1743 ms 64336 KB Output is correct
35 Correct 1714 ms 64164 KB Output is correct
36 Correct 1672 ms 63952 KB Output is correct
37 Correct 1675 ms 64128 KB Output is correct
38 Correct 1692 ms 64312 KB Output is correct
39 Correct 1272 ms 63272 KB Output is correct
40 Correct 1151 ms 59124 KB Output is correct
41 Correct 836 ms 53380 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47608 KB Output is correct
2 Correct 48 ms 47352 KB Output is correct
3 Correct 47 ms 47324 KB Output is correct
4 Correct 47 ms 47352 KB Output is correct
5 Correct 51 ms 47352 KB Output is correct
6 Correct 46 ms 47352 KB Output is correct
7 Correct 47 ms 47352 KB Output is correct
8 Correct 47 ms 47352 KB Output is correct
9 Correct 47 ms 47352 KB Output is correct
10 Correct 48 ms 47352 KB Output is correct
11 Correct 52 ms 47480 KB Output is correct
12 Correct 58 ms 47656 KB Output is correct
13 Correct 59 ms 47764 KB Output is correct
14 Correct 65 ms 47736 KB Output is correct
15 Correct 65 ms 47820 KB Output is correct
16 Correct 69 ms 47864 KB Output is correct
17 Correct 57 ms 47608 KB Output is correct
18 Correct 66 ms 47480 KB Output is correct
19 Execution timed out 3027 ms 110264 KB Time limit exceeded
20 Halted 0 ms 0 KB -