oj.uz

Submission #168242

# Submission time Handle Problem Language Result Execution time Memory
168242 2019-12-12T06:34:05 Z koste4ka Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
34 / 100
 3000 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 < unordered_map < int, int > > prec;

vector < unordered_map < 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 3 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 760 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 4 ms 760 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 4 ms 676 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 3 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 760 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 4 ms 760 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 4 ms 676 KB Output is correct
11 Correct 13 ms 1656 KB Output is correct
12 Correct 26 ms 5112 KB Output is correct
13 Correct 27 ms 5112 KB Output is correct
14 Correct 37 ms 5420 KB Output is correct
15 Correct 35 ms 5376 KB Output is correct
16 Correct 25 ms 5368 KB Output is correct
17 Correct 19 ms 4600 KB Output is correct
18 Correct 17 ms 2940 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 502 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 1143 ms 93880 KB Output is correct
2 Correct 982 ms 93892 KB Output is correct
3 Correct 568 ms 52096 KB Output is correct
4 Correct 547 ms 52088 KB Output is correct
5 Correct 554 ms 52076 KB Output is correct
6 Correct 396 ms 52072 KB Output is correct
7 Correct 390 ms 52088 KB Output is correct
8 Correct 503 ms 51448 KB Output is correct
9 Correct 84 ms 1144 KB Output is correct
10 Correct 499 ms 51448 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 3 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 760 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 4 ms 760 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 4 ms 676 KB Output is correct
11 Correct 13 ms 1656 KB Output is correct
12 Correct 26 ms 5112 KB Output is correct
13 Correct 27 ms 5112 KB Output is correct
14 Correct 37 ms 5420 KB Output is correct
15 Correct 35 ms 5376 KB Output is correct
16 Correct 25 ms 5368 KB Output is correct
17 Correct 19 ms 4600 KB Output is correct
18 Correct 17 ms 2940 KB Output is correct
19 Execution timed out 3055 ms 255144 KB Time limit exceeded
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 3 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 760 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 4 ms 760 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 4 ms 676 KB Output is correct
11 Correct 13 ms 1656 KB Output is correct
12 Correct 26 ms 5112 KB Output is correct
13 Correct 27 ms 5112 KB Output is correct
14 Correct 37 ms 5420 KB Output is correct
15 Correct 35 ms 5376 KB Output is correct
16 Correct 25 ms 5368 KB Output is correct
17 Correct 19 ms 4600 KB Output is correct
18 Correct 17 ms 2940 KB Output is correct
19 Runtime error 502 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -