oj.uz

Submission #168239

# Submission time Handle Problem Language Result Execution time Memory
168239 2019-12-12T06:23:37 Z koste4ka Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 862 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 < vector < int > > prec;

vector < vector < 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);
            }
            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, vector < int > (20));
    all.resize(n + 1, vector < set < int > > (20));
    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:71:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
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 Incorrect 3 ms 508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
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 Incorrect 3 ms 508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 256 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 862 ms 164380 KB Output is correct
2 Correct 755 ms 164552 KB Output is correct
3 Correct 416 ms 122788 KB Output is correct
4 Correct 403 ms 122744 KB Output is correct
5 Correct 418 ms 122720 KB Output is correct
6 Correct 333 ms 122616 KB Output is correct
7 Correct 337 ms 122488 KB Output is correct
8 Correct 358 ms 121592 KB Output is correct
9 Correct 67 ms 2680 KB Output is correct
10 Correct 355 ms 121592 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 Incorrect 3 ms 508 KB Output isn't correct
4 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 Incorrect 3 ms 508 KB Output isn't correct
4 Halted 0 ms 0 KB -