oj.uz

Submission #166353

# Submission time Handle Problem Language Result Execution time Memory
166353 2019-12-01T18:26:15 Z koste4ka Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 99468 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 = 3000;
    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 51 ms 47352 KB Output is correct
2 Correct 133 ms 47352 KB Output is correct
3 Correct 46 ms 47352 KB Output is correct
4 Correct 45 ms 47356 KB Output is correct
5 Correct 46 ms 47352 KB Output is correct
6 Correct 57 ms 47480 KB Output is correct
7 Correct 47 ms 47396 KB Output is correct
8 Correct 47 ms 47352 KB Output is correct
9 Correct 46 ms 47280 KB Output is correct
10 Correct 46 ms 47352 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 47352 KB Output is correct
2 Correct 133 ms 47352 KB Output is correct
3 Correct 46 ms 47352 KB Output is correct
4 Correct 45 ms 47356 KB Output is correct
5 Correct 46 ms 47352 KB Output is correct
6 Correct 57 ms 47480 KB Output is correct
7 Correct 47 ms 47396 KB Output is correct
8 Correct 47 ms 47352 KB Output is correct
9 Correct 46 ms 47280 KB Output is correct
10 Correct 46 ms 47352 KB Output is correct
11 Correct 55 ms 47500 KB Output is correct
12 Correct 60 ms 47640 KB Output is correct
13 Correct 60 ms 47604 KB Output is correct
14 Correct 68 ms 47608 KB Output is correct
15 Correct 74 ms 47648 KB Output is correct
16 Correct 81 ms 47656 KB Output is correct
17 Correct 62 ms 47608 KB Output is correct
18 Correct 72 ms 47352 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 738 ms 49688 KB Output is correct
2 Correct 871 ms 49660 KB Output is correct
3 Correct 780 ms 48204 KB Output is correct
4 Correct 878 ms 48140 KB Output is correct
5 Correct 729 ms 47992 KB Output is correct
6 Correct 1115 ms 48092 KB Output is correct
7 Correct 816 ms 48120 KB Output is correct
8 Correct 603 ms 47896 KB Output is correct
9 Correct 162 ms 47600 KB Output is correct
10 Correct 601 ms 47992 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 47352 KB Output is correct
2 Correct 133 ms 47352 KB Output is correct
3 Correct 46 ms 47352 KB Output is correct
4 Correct 45 ms 47356 KB Output is correct
5 Correct 46 ms 47352 KB Output is correct
6 Correct 57 ms 47480 KB Output is correct
7 Correct 47 ms 47396 KB Output is correct
8 Correct 47 ms 47352 KB Output is correct
9 Correct 46 ms 47280 KB Output is correct
10 Correct 46 ms 47352 KB Output is correct
11 Correct 55 ms 47500 KB Output is correct
12 Correct 60 ms 47640 KB Output is correct
13 Correct 60 ms 47604 KB Output is correct
14 Correct 68 ms 47608 KB Output is correct
15 Correct 74 ms 47648 KB Output is correct
16 Correct 81 ms 47656 KB Output is correct
17 Correct 62 ms 47608 KB Output is correct
18 Correct 72 ms 47352 KB Output is correct
19 Correct 1686 ms 58104 KB Output is correct
20 Correct 1726 ms 58104 KB Output is correct
21 Correct 2308 ms 58060 KB Output is correct
22 Correct 2364 ms 59028 KB Output is correct
23 Correct 2354 ms 59076 KB Output is correct
24 Correct 1649 ms 59092 KB Output is correct
25 Correct 1683 ms 59056 KB Output is correct
26 Correct 1613 ms 59156 KB Output is correct
27 Correct 1621 ms 59100 KB Output is correct
28 Correct 1647 ms 59124 KB Output is correct
29 Correct 1534 ms 59112 KB Output is correct
30 Correct 1622 ms 59180 KB Output is correct
31 Correct 1714 ms 59084 KB Output is correct
32 Correct 1606 ms 58964 KB Output is correct
33 Correct 1588 ms 59268 KB Output is correct
34 Correct 2074 ms 59052 KB Output is correct
35 Correct 2070 ms 59076 KB Output is correct
36 Correct 2106 ms 59156 KB Output is correct
37 Correct 2076 ms 59180 KB Output is correct
38 Correct 2112 ms 59172 KB Output is correct
39 Correct 1708 ms 58968 KB Output is correct
40 Correct 2138 ms 55604 KB Output is correct
41 Correct 1354 ms 49832 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 47352 KB Output is correct
2 Correct 133 ms 47352 KB Output is correct
3 Correct 46 ms 47352 KB Output is correct
4 Correct 45 ms 47356 KB Output is correct
5 Correct 46 ms 47352 KB Output is correct
6 Correct 57 ms 47480 KB Output is correct
7 Correct 47 ms 47396 KB Output is correct
8 Correct 47 ms 47352 KB Output is correct
9 Correct 46 ms 47280 KB Output is correct
10 Correct 46 ms 47352 KB Output is correct
11 Correct 55 ms 47500 KB Output is correct
12 Correct 60 ms 47640 KB Output is correct
13 Correct 60 ms 47604 KB Output is correct
14 Correct 68 ms 47608 KB Output is correct
15 Correct 74 ms 47648 KB Output is correct
16 Correct 81 ms 47656 KB Output is correct
17 Correct 62 ms 47608 KB Output is correct
18 Correct 72 ms 47352 KB Output is correct
19 Execution timed out 3066 ms 99468 KB Time limit exceeded
20 Halted 0 ms 0 KB -