oj.uz

Submission #152622

# Submission time Handle Problem Language Result Execution time Memory
152622 2019-09-08T15:34:35 Z leatherman Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 800 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;
    }
    ll tm = (tl + tr) / 2;
    if(pos <= tm)
    {
        now -> r = old -> r;
        now -> l = new node();
        upd(old -> l, now -> l, tl, tm, pos, val);
    } else
    {
        now -> l = old -> l;
        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 420 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 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 420 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 6 ms 1016 KB Output is correct
12 Correct 10 ms 2936 KB Output is correct
13 Correct 10 ms 2936 KB Output is correct
14 Correct 12 ms 2936 KB Output is correct
15 Correct 12 ms 3064 KB Output is correct
16 Correct 8 ms 1656 KB Output is correct
17 Correct 7 ms 1272 KB Output is correct
18 Correct 9 ms 2424 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 668 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 321 ms 66552 KB Output is correct
2 Correct 284 ms 66716 KB Output is correct
3 Correct 161 ms 12192 KB Output is correct
4 Correct 162 ms 12012 KB Output is correct
5 Correct 156 ms 12008 KB Output is correct
6 Correct 109 ms 17516 KB Output is correct
7 Correct 110 ms 17644 KB Output is correct
8 Correct 235 ms 51268 KB Output is correct
9 Correct 49 ms 760 KB Output is correct
10 Correct 211 ms 43680 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 420 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 6 ms 1016 KB Output is correct
12 Correct 10 ms 2936 KB Output is correct
13 Correct 10 ms 2936 KB Output is correct
14 Correct 12 ms 2936 KB Output is correct
15 Correct 12 ms 3064 KB Output is correct
16 Correct 8 ms 1656 KB Output is correct
17 Correct 7 ms 1272 KB Output is correct
18 Correct 9 ms 2424 KB Output is correct
19 Correct 800 ms 139176 KB Output is correct
20 Correct 716 ms 139160 KB Output is correct
21 Correct 617 ms 139076 KB Output is correct
22 Correct 625 ms 139104 KB Output is correct
23 Correct 593 ms 139060 KB Output is correct
24 Correct 256 ms 23524 KB Output is correct
25 Correct 254 ms 23680 KB Output is correct
26 Correct 359 ms 23656 KB Output is correct
27 Correct 383 ms 23668 KB Output is correct
28 Correct 399 ms 23616 KB Output is correct
29 Correct 401 ms 23640 KB Output is correct
30 Correct 401 ms 23704 KB Output is correct
31 Correct 400 ms 23548 KB Output is correct
32 Correct 394 ms 23552 KB Output is correct
33 Correct 456 ms 23496 KB Output is correct
34 Correct 223 ms 23524 KB Output is correct
35 Correct 223 ms 23524 KB Output is correct
36 Correct 226 ms 23528 KB Output is correct
37 Correct 222 ms 23608 KB Output is correct
38 Correct 222 ms 23524 KB Output is correct
39 Correct 413 ms 62640 KB Output is correct
40 Correct 281 ms 34008 KB Output is correct
41 Correct 454 ms 89600 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 420 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 6 ms 1016 KB Output is correct
12 Correct 10 ms 2936 KB Output is correct
13 Correct 10 ms 2936 KB Output is correct
14 Correct 12 ms 2936 KB Output is correct
15 Correct 12 ms 3064 KB Output is correct
16 Correct 8 ms 1656 KB Output is correct
17 Correct 7 ms 1272 KB Output is correct
18 Correct 9 ms 2424 KB Output is correct
19 Runtime error 668 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -