oj.uz

Submission #168243

# Submission time Handle Problem Language Result Execution time Memory
168243 2019-12-12T06:34:53 Z koste4ka Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
34 / 100
 910 ms 262148 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 n;

vector < cc_hash_table < int, int > > prec;

vector < cc_hash_table < int, set < int > > > all;

vector < int > a;

vector < pair < int, int > > need;

void go(int l, int r, int st) {
    if (r < l) {
        return;
    }
    int now;
    int mid;
    while (st >= 0) {
        now = (1 << st);
        mid = r / now * now;
        if (mid - now + 1 >= l) {
            need.pb({mid, st});
            if (st) {
                go(l, mid - now, st);
                go(mid + 1, r, st);
            } else {
                go(l, mid - 1, st);
                go(mid + 1, r, st);
            }
            return;
        }
        --st;
    }
    return;
}

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 n, m;
    cin >> n >> m;
    a.resize(n);
    prec.resize(n + 1);
    all.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        all[i][0].insert(a[i]);
    }
    int now;
    int x;
    for (int st = 1; st < 20; ++st) {
        now = (1 << st);
        for (int i = 1; i <= n; ++i) {
            if (i % now) {
                continue;
            }
            prec[i][st] = max(prec[i][st - 1], prec[i - now / 2][st - 1]);
            x = *all[i - now / 2][st - 1].rbegin();
            if (*all[i][st - 1].begin() < x) {
                auto it = all[i][st - 1].lower_bound(x);
                --it;
                prec[i][st] = max(prec[i][st], x + *it);
            }
            for (int j = 0; j < now; ++j) {
                all[i][st].insert(a[i - j]);
            }
        }
    }
    int l, r, k;
    int res;
    int best;
    while (m--) {
        cin >> l >> r >> k;
        need.clear();
        go(l, r, 19);
        sort(need.begin(), need.end());
        res = 0;
        best = 0;
        for (auto i : need) {
            if (*all[i.F][i.S].begin() < best) {
                auto it = all[i.F][i.S].lower_bound(best);
                --it;
                res = max(res, best + *it);
            }
            res = max(res, prec[i.F][i.S]);
            best = max(best, *all[i.F][i.S].rbegin());
        }
        cout << (res <= k) << '\n';
    }
    return 0;
}

Compilation message

sortbooks.cpp:74:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
sortbooks.cpp: In function 'void go(int, int, int)':
sortbooks.cpp:50:5: warning: assuming signed overflow does not occur when assuming that (X - c) <= X is always true [-Wstrict-overflow]
     if (r < l) {
     ^~
sortbooks.cpp:50:5: warning: assuming signed overflow does not occur when assuming that (X - c) <= X is always true [-Wstrict-overflow]
     if (r < l) {
     ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 4 ms 888 KB Output is correct
7 Correct 4 ms 888 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 4 ms 888 KB Output is correct
7 Correct 4 ms 888 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 11 ms 1912 KB Output is correct
12 Correct 23 ms 6140 KB Output is correct
13 Correct 25 ms 6136 KB Output is correct
14 Correct 29 ms 6264 KB Output is correct
15 Correct 29 ms 6264 KB Output is correct
16 Correct 22 ms 6264 KB Output is correct
17 Correct 18 ms 5368 KB Output is correct
18 Correct 15 ms 3832 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 305 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 910 ms 112460 KB Output is correct
2 Correct 870 ms 112736 KB Output is correct
3 Correct 513 ms 70776 KB Output is correct
4 Correct 452 ms 70708 KB Output is correct
5 Correct 441 ms 70896 KB Output is correct
6 Correct 354 ms 70804 KB Output is correct
7 Correct 343 ms 70864 KB Output is correct
8 Correct 396 ms 70112 KB Output is correct
9 Correct 71 ms 1016 KB Output is correct
10 Correct 392 ms 70188 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 4 ms 888 KB Output is correct
7 Correct 4 ms 888 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 11 ms 1912 KB Output is correct
12 Correct 23 ms 6140 KB Output is correct
13 Correct 25 ms 6136 KB Output is correct
14 Correct 29 ms 6264 KB Output is correct
15 Correct 29 ms 6264 KB Output is correct
16 Correct 22 ms 6264 KB Output is correct
17 Correct 18 ms 5368 KB Output is correct
18 Correct 15 ms 3832 KB Output is correct
19 Runtime error 721 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 4 ms 888 KB Output is correct
7 Correct 4 ms 888 KB Output is correct
8 Correct 3 ms 760 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 632 KB Output is correct
11 Correct 11 ms 1912 KB Output is correct
12 Correct 23 ms 6140 KB Output is correct
13 Correct 25 ms 6136 KB Output is correct
14 Correct 29 ms 6264 KB Output is correct
15 Correct 29 ms 6264 KB Output is correct
16 Correct 22 ms 6264 KB Output is correct
17 Correct 18 ms 5368 KB Output is correct
18 Correct 15 ms 3832 KB Output is correct
19 Runtime error 305 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -