oj.uz

Submission #152618

# Submission time Handle Problem Language Result Execution time Memory
152618 2019-09-08T15:12:14 Z leatherman Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 731 ms 262148 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 = 1e6 + 2;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct node
{
    ll val;
    node *l,*r;
    node() : val(0), l(nullptr), r(nullptr){}
};
node *root[N],*mb;
ll n,Q,a[N],x,pos,l,r,k;
vector<pair<ll, ll> > v;
void build(node *v,ll tl,ll tr)
{
    if(tl == tr) return;
    ll tm = (tl + tr) / 2;
    v -> l = new node();
    v -> r = new node();
    build(v -> l, tl, tm);
    build(v -> r, tm + 1, tr);
}
void upd(node *old, node *now,ll tl,ll tr,ll pos,ll val)
{
    if(tl == tr)
    {
        now -> val = val;
        return;
    }
    now -> l = old -> l;
    now -> r = old -> r;
    ll tm = (tl + tr) / 2;
    if(pos <= tm)
    {
        now -> l = new node();
        upd(old -> l, now -> l, tl, tm, pos, val);
    } else
    {
        now -> r= new node();
        upd(old -> r, now -> r, tm + 1, tr, pos, val);
    }
    now -> val = max((now -> l) -> val, (now -> r) -> val);
}
ll get(node *v,ll tl,ll tr,ll l,ll r)
{
    if(l > r) return 0;
    if(tl == l && tr == r) return v -> val;
    ll tm = (tl + tr) / 2;
    return max(get(v -> l, tl, tm, l, min(r, tm)), get(v -> r, tm + 1, tr, max(l, tm + 1), r));
}
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];
    root[n + 1] = new node();
    build(root[n + 1], 1, n);
    for(int i = n; i >= 1; i--)
    {
        x = a[i];
        root[i] = new node();
        root[i] -> val = root[i + 1] -> val;
        root[i] -> l = root[i + 1] -> l;
        root[i] -> r = root[i + 1] -> r;
        while(!v.empty() && v.back().fi < x)
        {
            pos = v.back().se;
            mb = new node();
            upd(root[i], mb, 1, n, pos, a[pos] + x);
            root[i] = mb;
            v.pop_back();
        }
        v.PB({x, i});
    }
    while(Q--)
    {
        cin>>l>>r>>k;
        x = get(root[l], 1, n, l, r);
        cout<<(x <= k)<<endl;
    }
    return 0;
}
/*
5 2
3 5 1 8 2
1 3 6
2 5 3
*/

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 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 504 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 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 6 ms 1144 KB Output is correct
12 Correct 10 ms 2936 KB Output is correct
13 Correct 10 ms 2936 KB Output is correct
14 Correct 13 ms 3064 KB Output is correct
15 Correct 13 ms 3036 KB Output is correct
16 Correct 9 ms 1656 KB Output is correct
17 Correct 7 ms 1272 KB Output is correct
18 Correct 9 ms 2428 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 616 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 317 ms 66652 KB Output is correct
2 Correct 271 ms 66592 KB Output is correct
3 Correct 170 ms 11980 KB Output is correct
4 Correct 174 ms 12012 KB Output is correct
5 Correct 162 ms 11980 KB Output is correct
6 Correct 113 ms 17532 KB Output is correct
7 Correct 114 ms 17664 KB Output is correct
8 Correct 210 ms 51196 KB Output is correct
9 Correct 53 ms 760 KB Output is correct
10 Correct 191 ms 43420 KB Output is correct

Subtask #5
30.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 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 6 ms 1144 KB Output is correct
12 Correct 10 ms 2936 KB Output is correct
13 Correct 10 ms 2936 KB Output is correct
14 Correct 13 ms 3064 KB Output is correct
15 Correct 13 ms 3036 KB Output is correct
16 Correct 9 ms 1656 KB Output is correct
17 Correct 7 ms 1272 KB Output is correct
18 Correct 9 ms 2428 KB Output is correct
19 Correct 731 ms 139148 KB Output is correct
20 Correct 729 ms 139164 KB Output is correct
21 Correct 645 ms 139236 KB Output is correct
22 Correct 597 ms 139148 KB Output is correct
23 Correct 598 ms 139260 KB Output is correct
24 Correct 261 ms 23688 KB Output is correct
25 Correct 260 ms 23628 KB Output is correct
26 Correct 386 ms 23696 KB Output is correct
27 Correct 370 ms 23608 KB Output is correct
28 Correct 402 ms 23608 KB Output is correct
29 Correct 422 ms 23524 KB Output is correct
30 Correct 417 ms 23916 KB Output is correct
31 Correct 424 ms 23672 KB Output is correct
32 Correct 427 ms 23748 KB Output is correct
33 Correct 420 ms 23816 KB Output is correct
34 Correct 233 ms 23912 KB Output is correct
35 Correct 231 ms 23780 KB Output is correct
36 Correct 230 ms 23692 KB Output is correct
37 Correct 230 ms 23652 KB Output is correct
38 Correct 231 ms 23652 KB Output is correct
39 Correct 420 ms 62804 KB Output is correct
40 Correct 283 ms 34152 KB Output is correct
41 Correct 459 ms 89996 KB Output is correct

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 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 6 ms 1144 KB Output is correct
12 Correct 10 ms 2936 KB Output is correct
13 Correct 10 ms 2936 KB Output is correct
14 Correct 13 ms 3064 KB Output is correct
15 Correct 13 ms 3036 KB Output is correct
16 Correct 9 ms 1656 KB Output is correct
17 Correct 7 ms 1272 KB Output is correct
18 Correct 9 ms 2428 KB Output is correct
19 Runtime error 616 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -