oj.uz

Submission #166352

# Submission time Handle Problem Language Result Execution time Memory
166352 2019-12-01T18:25:03 Z koste4ka Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
34 / 100
 3000 ms 99104 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 = 1000;
    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 52 ms 47356 KB Output is correct
2 Correct 46 ms 47356 KB Output is correct
3 Correct 47 ms 47352 KB Output is correct
4 Correct 47 ms 47352 KB Output is correct
5 Correct 56 ms 47352 KB Output is correct
6 Correct 47 ms 47352 KB Output is correct
7 Correct 47 ms 47416 KB Output is correct
8 Correct 47 ms 47352 KB Output is correct
9 Correct 47 ms 47352 KB Output is correct
10 Correct 47 ms 47352 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 47356 KB Output is correct
2 Correct 46 ms 47356 KB Output is correct
3 Correct 47 ms 47352 KB Output is correct
4 Correct 47 ms 47352 KB Output is correct
5 Correct 56 ms 47352 KB Output is correct
6 Correct 47 ms 47352 KB Output is correct
7 Correct 47 ms 47416 KB Output is correct
8 Correct 47 ms 47352 KB Output is correct
9 Correct 47 ms 47352 KB Output is correct
10 Correct 47 ms 47352 KB Output is correct
11 Correct 51 ms 47480 KB Output is correct
12 Correct 54 ms 47736 KB Output is correct
13 Correct 55 ms 47736 KB Output is correct
14 Correct 60 ms 47772 KB Output is correct
15 Correct 61 ms 47720 KB Output is correct
16 Correct 59 ms 47736 KB Output is correct
17 Correct 54 ms 47692 KB Output is correct
18 Correct 56 ms 47480 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 52108 KB Output is correct
2 Correct 832 ms 52100 KB Output is correct
3 Correct 351 ms 49144 KB Output is correct
4 Correct 354 ms 49272 KB Output is correct
5 Correct 332 ms 49256 KB Output is correct
6 Correct 383 ms 49280 KB Output is correct
7 Correct 386 ms 49176 KB Output is correct
8 Correct 292 ms 49212 KB Output is correct
9 Correct 160 ms 48732 KB Output is correct
10 Correct 290 ms 49092 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 47356 KB Output is correct
2 Correct 46 ms 47356 KB Output is correct
3 Correct 47 ms 47352 KB Output is correct
4 Correct 47 ms 47352 KB Output is correct
5 Correct 56 ms 47352 KB Output is correct
6 Correct 47 ms 47352 KB Output is correct
7 Correct 47 ms 47416 KB Output is correct
8 Correct 47 ms 47352 KB Output is correct
9 Correct 47 ms 47352 KB Output is correct
10 Correct 47 ms 47352 KB Output is correct
11 Correct 51 ms 47480 KB Output is correct
12 Correct 54 ms 47736 KB Output is correct
13 Correct 55 ms 47736 KB Output is correct
14 Correct 60 ms 47772 KB Output is correct
15 Correct 61 ms 47720 KB Output is correct
16 Correct 59 ms 47736 KB Output is correct
17 Correct 54 ms 47692 KB Output is correct
18 Correct 56 ms 47480 KB Output is correct
19 Correct 1387 ms 59064 KB Output is correct
20 Correct 1399 ms 59052 KB Output is correct
21 Execution timed out 3042 ms 58984 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 47356 KB Output is correct
2 Correct 46 ms 47356 KB Output is correct
3 Correct 47 ms 47352 KB Output is correct
4 Correct 47 ms 47352 KB Output is correct
5 Correct 56 ms 47352 KB Output is correct
6 Correct 47 ms 47352 KB Output is correct
7 Correct 47 ms 47416 KB Output is correct
8 Correct 47 ms 47352 KB Output is correct
9 Correct 47 ms 47352 KB Output is correct
10 Correct 47 ms 47352 KB Output is correct
11 Correct 51 ms 47480 KB Output is correct
12 Correct 54 ms 47736 KB Output is correct
13 Correct 55 ms 47736 KB Output is correct
14 Correct 60 ms 47772 KB Output is correct
15 Correct 61 ms 47720 KB Output is correct
16 Correct 59 ms 47736 KB Output is correct
17 Correct 54 ms 47692 KB Output is correct
18 Correct 56 ms 47480 KB Output is correct
19 Execution timed out 3052 ms 99104 KB Time limit exceeded
20 Halted 0 ms 0 KB -