oj.uz

Submission #151408

# Submission time Handle Problem Language Result Execution time Memory
151408 2019-09-02T18:06:48 Z leatherman Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 768 ms 62840 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define ll int
#define ld long double
#define endl "\n"
#define fi first
#define se second
#define y1 sadjfskldf
#define PB push_back
#define sqr(x) ((x) * (x))
#define all(x) x.begin(), x.end()
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

const ll N = 2e5 + 200;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct trees
{
    ll ans;
    vector<ll> val;
};
trees t[4 * N];
ll a[N],global,n,Q,l,r,x,k;
ll quest(ll mx,vector<ll> &v)
{
    ll pos = lower_bound(all(v), mx) - v.begin();
    if(!pos) return 0;
    return mx + v[--pos];
}
void build(ll v,ll tl,ll tr)
{
    if(tl == tr)
    {
        t[v].val.PB(a[tl]);
        return;
    }
    ll tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
    for(auto x : t[2 * v].val) t[v].val.PB(x);
    for(auto x : t[2 * v + 1].val) t[v].val.PB(x);
    sort(all(t[v].val));
    t[v].ans = max(max(t[2 * v].ans, t[2 * v + 1].ans), quest((t[2 * v].val).back(), (t[2 * v + 1].val)));
}
ll get(ll v,ll tl,ll tr,ll l, ll r)
{
    if(l > r) return 0;
    if(tl == l && tr == r)
    {
        ll ans = t[v].ans;
        ans = max(ans, quest(global, t[v].val));
        global = max(global, t[v].val.back());
        return ans;
    }
    ll tm = (tl + tr) / 2,x,y;
    x = get(2 * v, tl, tm, l, min(tm, r));
    y = get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
    return max(x, y);
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>Q;
    for(int i = 1; i <= n; i++) cin>>a[i];
    build(1, 1, n);
    while(Q--)
    {
        cin>>l>>r>>k;
        global = 0;
        x = get(1, 1, n, l, r);
        if(x <= k) cout<<1<<endl;
        else cout<<0<<endl;
    }
    return 0;
}
/*
8 1
5 4 3 1 6 7 8 2
2 5
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25336 KB Output is correct
2 Correct 25 ms 25464 KB Output is correct
3 Correct 25 ms 25468 KB Output is correct
4 Correct 24 ms 25464 KB Output is correct
5 Correct 24 ms 25388 KB Output is correct
6 Correct 25 ms 25464 KB Output is correct
7 Correct 25 ms 25464 KB Output is correct
8 Correct 24 ms 25464 KB Output is correct
9 Correct 29 ms 25464 KB Output is correct
10 Correct 24 ms 25468 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25336 KB Output is correct
2 Correct 25 ms 25464 KB Output is correct
3 Correct 25 ms 25468 KB Output is correct
4 Correct 24 ms 25464 KB Output is correct
5 Correct 24 ms 25388 KB Output is correct
6 Correct 25 ms 25464 KB Output is correct
7 Correct 25 ms 25464 KB Output is correct
8 Correct 24 ms 25464 KB Output is correct
9 Correct 29 ms 25464 KB Output is correct
10 Correct 24 ms 25468 KB Output is correct
11 Correct 28 ms 25684 KB Output is correct
12 Correct 32 ms 26104 KB Output is correct
13 Correct 32 ms 26104 KB Output is correct
14 Correct 33 ms 26232 KB Output is correct
15 Correct 34 ms 26232 KB Output is correct
16 Correct 32 ms 26232 KB Output is correct
17 Correct 30 ms 25976 KB Output is correct
18 Correct 32 ms 26184 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 196 ms 62840 KB Execution killed with signal 11 (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 320 ms 41296 KB Output is correct
2 Correct 299 ms 41312 KB Output is correct
3 Correct 246 ms 41328 KB Output is correct
4 Correct 244 ms 41200 KB Output is correct
5 Correct 249 ms 41288 KB Output is correct
6 Correct 194 ms 41168 KB Output is correct
7 Correct 196 ms 41080 KB Output is correct
8 Correct 219 ms 40944 KB Output is correct
9 Correct 77 ms 26948 KB Output is correct
10 Correct 214 ms 40948 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25336 KB Output is correct
2 Correct 25 ms 25464 KB Output is correct
3 Correct 25 ms 25468 KB Output is correct
4 Correct 24 ms 25464 KB Output is correct
5 Correct 24 ms 25388 KB Output is correct
6 Correct 25 ms 25464 KB Output is correct
7 Correct 25 ms 25464 KB Output is correct
8 Correct 24 ms 25464 KB Output is correct
9 Correct 29 ms 25464 KB Output is correct
10 Correct 24 ms 25468 KB Output is correct
11 Correct 28 ms 25684 KB Output is correct
12 Correct 32 ms 26104 KB Output is correct
13 Correct 32 ms 26104 KB Output is correct
14 Correct 33 ms 26232 KB Output is correct
15 Correct 34 ms 26232 KB Output is correct
16 Correct 32 ms 26232 KB Output is correct
17 Correct 30 ms 25976 KB Output is correct
18 Correct 32 ms 26184 KB Output is correct
19 Correct 762 ms 60600 KB Output is correct
20 Correct 768 ms 60700 KB Output is correct
21 Correct 675 ms 60524 KB Output is correct
22 Correct 680 ms 60296 KB Output is correct
23 Correct 665 ms 60384 KB Output is correct
24 Correct 456 ms 60140 KB Output is correct
25 Correct 478 ms 60356 KB Output is correct
26 Correct 544 ms 60408 KB Output is correct
27 Correct 545 ms 60528 KB Output is correct
28 Correct 590 ms 60652 KB Output is correct
29 Correct 574 ms 60484 KB Output is correct
30 Correct 562 ms 60524 KB Output is correct
31 Correct 570 ms 60524 KB Output is correct
32 Correct 567 ms 60512 KB Output is correct
33 Correct 568 ms 60564 KB Output is correct
34 Correct 423 ms 60116 KB Output is correct
35 Correct 431 ms 60272 KB Output is correct
36 Correct 422 ms 59884 KB Output is correct
37 Correct 412 ms 59840 KB Output is correct
38 Correct 425 ms 60328 KB Output is correct
39 Correct 525 ms 58976 KB Output is correct
40 Correct 337 ms 46448 KB Output is correct
41 Correct 499 ms 58636 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25336 KB Output is correct
2 Correct 25 ms 25464 KB Output is correct
3 Correct 25 ms 25468 KB Output is correct
4 Correct 24 ms 25464 KB Output is correct
5 Correct 24 ms 25388 KB Output is correct
6 Correct 25 ms 25464 KB Output is correct
7 Correct 25 ms 25464 KB Output is correct
8 Correct 24 ms 25464 KB Output is correct
9 Correct 29 ms 25464 KB Output is correct
10 Correct 24 ms 25468 KB Output is correct
11 Correct 28 ms 25684 KB Output is correct
12 Correct 32 ms 26104 KB Output is correct
13 Correct 32 ms 26104 KB Output is correct
14 Correct 33 ms 26232 KB Output is correct
15 Correct 34 ms 26232 KB Output is correct
16 Correct 32 ms 26232 KB Output is correct
17 Correct 30 ms 25976 KB Output is correct
18 Correct 32 ms 26184 KB Output is correct
19 Runtime error 196 ms 62840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -