oj.uz

Submission #153576

# Submission time Handle Problem Language Result Execution time Memory
153576 2019-09-14T16:36:28 Z leatherman Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 1779 ms 118936 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 fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 2e5;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

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

template <typename T> void vout(T s){cout << s << endl;exit(0);}

ll ans[MAXN];

vector <ll> v[MAXN];

struct qry{
    ll l, r, idx, k;
};

bool cmp(qry a, qry b){
    if(a.l > b.l)return 1;
    if(a.l < b.l)return 0;
    return (a.idx < b.idx);
}

ll t[4 * MAXN];

void upd(ll v,ll tl,ll tr,ll pos,ll val)
{
    if(tl == tr)
    {
        t[v] = max(t[v], val);
        return;
    }
    ll tm = (tl + tr) / 2;
    if(pos <= tm)
        upd(2 * v, tl, tm, pos, val);
    else
        upd(2 * v + 1, tm + 1, tr, pos, val);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}
ll get(ll v,ll tl,ll tr,ll l,ll r)
{
    if(l > r)
        return 0;
    if(tl == l && tr == r)
        return t[v];
    ll tm = (tl + tr) / 2;
    return max(get(2 * v, tl, tm, l, min(r, tm)), get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    ll n, m;
    cin >> n >> m;

    vector <ll> w(n + 1), le(n + 1);

    for(int i = 1; i <= n; i++)cin >> w[i];
    vector<pair<ll, ll> > v1;
    v1.p_b({1e18, 0});
    for(int i = 1; i <= n; i++)
    {
        ll x  = w[i];
        while(x >= v1.back().fi) v1.pop_back();
        v[v1.back().se].p_b(i);
        v1.p_b({x, i});
    }
    vector <qry> c(m);

    ll uk = n;

    for(int i = 0; i < m; i++){
        cin >> c[i].l >> c[i].r >> c[i].k;
        c[i].idx = i;
    }

    sort(all(c), cmp);

    for(auto kek : c){
        while(kek.l < uk){
            for(auto j : v[uk - 1]){
                upd(1, 1, n, j, w[uk - 1] + w[j]);
            }
            uk--;
        }
        ans[kek.idx] = (get(1, 1, n, kek.l, kek.r) <= kek.k);
    }

    for(int i = 0; i < m; i++)cout << ans[i] << "\n";

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 26744 KB Output is correct
2 Correct 25 ms 26744 KB Output is correct
3 Correct 26 ms 26748 KB Output is correct
4 Correct 25 ms 26744 KB Output is correct
5 Correct 25 ms 26744 KB Output is correct
6 Correct 27 ms 26744 KB Output is correct
7 Correct 27 ms 26744 KB Output is correct
8 Correct 26 ms 26744 KB Output is correct
9 Correct 26 ms 26812 KB Output is correct
10 Correct 26 ms 26744 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 26744 KB Output is correct
2 Correct 25 ms 26744 KB Output is correct
3 Correct 26 ms 26748 KB Output is correct
4 Correct 25 ms 26744 KB Output is correct
5 Correct 25 ms 26744 KB Output is correct
6 Correct 27 ms 26744 KB Output is correct
7 Correct 27 ms 26744 KB Output is correct
8 Correct 26 ms 26744 KB Output is correct
9 Correct 26 ms 26812 KB Output is correct
10 Correct 26 ms 26744 KB Output is correct
11 Correct 28 ms 26900 KB Output is correct
12 Correct 30 ms 27196 KB Output is correct
13 Correct 30 ms 27160 KB Output is correct
14 Correct 32 ms 27228 KB Output is correct
15 Correct 32 ms 27256 KB Output is correct
16 Correct 31 ms 27212 KB Output is correct
17 Correct 30 ms 27176 KB Output is correct
18 Correct 27 ms 27256 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1736 ms 118696 KB Output is correct
2 Correct 1764 ms 118680 KB Output is correct
3 Correct 1779 ms 118904 KB Output is correct
4 Correct 1743 ms 118832 KB Output is correct
5 Correct 1466 ms 91596 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 36344 KB Output is correct
2 Correct 155 ms 36316 KB Output is correct
3 Correct 135 ms 33392 KB Output is correct
4 Correct 137 ms 33336 KB Output is correct
5 Correct 134 ms 33328 KB Output is correct
6 Correct 128 ms 33580 KB Output is correct
7 Correct 127 ms 33644 KB Output is correct
8 Correct 134 ms 35016 KB Output is correct
9 Correct 89 ms 30840 KB Output is correct
10 Correct 130 ms 34524 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 26744 KB Output is correct
2 Correct 25 ms 26744 KB Output is correct
3 Correct 26 ms 26748 KB Output is correct
4 Correct 25 ms 26744 KB Output is correct
5 Correct 25 ms 26744 KB Output is correct
6 Correct 27 ms 26744 KB Output is correct
7 Correct 27 ms 26744 KB Output is correct
8 Correct 26 ms 26744 KB Output is correct
9 Correct 26 ms 26812 KB Output is correct
10 Correct 26 ms 26744 KB Output is correct
11 Correct 28 ms 26900 KB Output is correct
12 Correct 30 ms 27196 KB Output is correct
13 Correct 30 ms 27160 KB Output is correct
14 Correct 32 ms 27228 KB Output is correct
15 Correct 32 ms 27256 KB Output is correct
16 Correct 31 ms 27212 KB Output is correct
17 Correct 30 ms 27176 KB Output is correct
18 Correct 27 ms 27256 KB Output is correct
19 Correct 334 ms 46004 KB Output is correct
20 Correct 337 ms 45896 KB Output is correct
21 Correct 314 ms 45948 KB Output is correct
22 Correct 314 ms 45916 KB Output is correct
23 Correct 319 ms 45976 KB Output is correct
24 Correct 268 ms 40004 KB Output is correct
25 Correct 268 ms 39812 KB Output is correct
26 Correct 274 ms 39836 KB Output is correct
27 Correct 280 ms 39776 KB Output is correct
28 Correct 282 ms 39940 KB Output is correct
29 Correct 279 ms 39760 KB Output is correct
30 Correct 280 ms 40044 KB Output is correct
31 Correct 280 ms 39916 KB Output is correct
32 Correct 281 ms 39952 KB Output is correct
33 Correct 282 ms 39816 KB Output is correct
34 Correct 264 ms 39804 KB Output is correct
35 Correct 280 ms 39916 KB Output is correct
36 Correct 263 ms 39804 KB Output is correct
37 Correct 256 ms 40044 KB Output is correct
38 Correct 284 ms 39872 KB Output is correct
39 Correct 263 ms 41836 KB Output is correct
40 Correct 219 ms 38856 KB Output is correct
41 Correct 281 ms 42556 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 26744 KB Output is correct
2 Correct 25 ms 26744 KB Output is correct
3 Correct 26 ms 26748 KB Output is correct
4 Correct 25 ms 26744 KB Output is correct
5 Correct 25 ms 26744 KB Output is correct
6 Correct 27 ms 26744 KB Output is correct
7 Correct 27 ms 26744 KB Output is correct
8 Correct 26 ms 26744 KB Output is correct
9 Correct 26 ms 26812 KB Output is correct
10 Correct 26 ms 26744 KB Output is correct
11 Correct 28 ms 26900 KB Output is correct
12 Correct 30 ms 27196 KB Output is correct
13 Correct 30 ms 27160 KB Output is correct
14 Correct 32 ms 27228 KB Output is correct
15 Correct 32 ms 27256 KB Output is correct
16 Correct 31 ms 27212 KB Output is correct
17 Correct 30 ms 27176 KB Output is correct
18 Correct 27 ms 27256 KB Output is correct
19 Correct 1736 ms 118696 KB Output is correct
20 Correct 1764 ms 118680 KB Output is correct
21 Correct 1779 ms 118904 KB Output is correct
22 Correct 1743 ms 118832 KB Output is correct
23 Correct 1466 ms 91596 KB Output is correct
24 Correct 160 ms 36344 KB Output is correct
25 Correct 155 ms 36316 KB Output is correct
26 Correct 135 ms 33392 KB Output is correct
27 Correct 137 ms 33336 KB Output is correct
28 Correct 134 ms 33328 KB Output is correct
29 Correct 128 ms 33580 KB Output is correct
30 Correct 127 ms 33644 KB Output is correct
31 Correct 134 ms 35016 KB Output is correct
32 Correct 89 ms 30840 KB Output is correct
33 Correct 130 ms 34524 KB Output is correct
34 Correct 334 ms 46004 KB Output is correct
35 Correct 337 ms 45896 KB Output is correct
36 Correct 314 ms 45948 KB Output is correct
37 Correct 314 ms 45916 KB Output is correct
38 Correct 319 ms 45976 KB Output is correct
39 Correct 268 ms 40004 KB Output is correct
40 Correct 268 ms 39812 KB Output is correct
41 Correct 274 ms 39836 KB Output is correct
42 Correct 280 ms 39776 KB Output is correct
43 Correct 282 ms 39940 KB Output is correct
44 Correct 279 ms 39760 KB Output is correct
45 Correct 280 ms 40044 KB Output is correct
46 Correct 280 ms 39916 KB Output is correct
47 Correct 281 ms 39952 KB Output is correct
48 Correct 282 ms 39816 KB Output is correct
49 Correct 264 ms 39804 KB Output is correct
50 Correct 280 ms 39916 KB Output is correct
51 Correct 263 ms 39804 KB Output is correct
52 Correct 256 ms 40044 KB Output is correct
53 Correct 284 ms 39872 KB Output is correct
54 Correct 263 ms 41836 KB Output is correct
55 Correct 219 ms 38856 KB Output is correct
56 Correct 281 ms 42556 KB Output is correct
57 Correct 1752 ms 118644 KB Output is correct
58 Correct 1757 ms 118728 KB Output is correct
59 Correct 1708 ms 118640 KB Output is correct
60 Correct 1746 ms 118936 KB Output is correct
61 Correct 1713 ms 118860 KB Output is correct
62 Correct 1704 ms 118768 KB Output is correct
63 Correct 1380 ms 91528 KB Output is correct
64 Correct 1354 ms 91564 KB Output is correct
65 Correct 1437 ms 91580 KB Output is correct
66 Correct 1430 ms 91512 KB Output is correct
67 Correct 1422 ms 91516 KB Output is correct
68 Correct 1408 ms 91640 KB Output is correct
69 Correct 1421 ms 91584 KB Output is correct
70 Correct 1423 ms 91592 KB Output is correct
71 Correct 1430 ms 91652 KB Output is correct
72 Correct 1417 ms 91516 KB Output is correct
73 Correct 1314 ms 91704 KB Output is correct
74 Correct 1347 ms 91568 KB Output is correct
75 Correct 1307 ms 91592 KB Output is correct
76 Correct 1314 ms 91564 KB Output is correct
77 Correct 1304 ms 91612 KB Output is correct
78 Correct 1405 ms 100592 KB Output is correct
79 Correct 1020 ms 83340 KB Output is correct
80 Correct 1322 ms 105412 KB Output is correct