oj.uz

Submission #153462

# Submission time Handle Problem Language Result Execution time Memory
153462 2019-09-14T08:24:14 Z leatherman Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 3000 ms 125048 KB 
#include <bits/stdc++.h>

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

#define ll long long
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sqr(x) (x)*(x)
#define PB push_back

using namespace std;
typedef long double ld;
const ll MOD = 1e9 + 7;
const ll N = 1e6 + 200;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
vector<pair<ll, ll> > v;
vector<ll> of[N],q[N];
pair<ll, ll> b[N];
ll ans[N],t[4 * N],a[N],l,r,x,k,limit,n,Q;
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();cin.tie(0);cout.tie(0);
    cin>>n>>Q;
    for(int i = 1; i <= n; i++) cin>>a[i];
    for(int i = n; i >= 1; i--)
    {
        x  = a[i];
        while(!v.empty() && x > v.back().fi)
        {
            of[i].PB(v.back().se);
            v.pop_back();
        }
        v.PB({x, i});
    }
    for(int i = 1; i <= Q; i++)
    {
        cin>>l>>r>>k;
        b[i] = {r, k};
        q[l].PB(i);
    }
    limit = n;
    for(int l = n; l >= 1; l--) if(!q[l].empty())
    for(auto i : q[l])
    {
        r = b[i].fi;
        while(limit >= l)
        {
            for(auto j : of[limit]) upd(1, 1, n, j, a[j] + a[limit]);
            limit--;
        }
        x = get(1, 1, n, l, r);
//        cout<<l<<" "<<r<<" = "<<x<<endl;
        ans[i] = (x <= b[i].se);
    }
    for(int i = 1; i <= Q; i++) cout<<ans[i]<<endl;
    return 0;
}
/*
8 6
5 4 3 1 6 7 8 2
1 5 0
2 5 0
3 5 0
4 5 0
5 5 0
1 8 0
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47356 KB Output is correct
2 Correct 44 ms 47432 KB Output is correct
3 Correct 47 ms 47352 KB Output is correct
4 Correct 45 ms 47352 KB Output is correct
5 Correct 45 ms 47352 KB Output is correct
6 Correct 48 ms 47356 KB Output is correct
7 Correct 48 ms 47416 KB Output is correct
8 Correct 48 ms 47376 KB Output is correct
9 Correct 47 ms 47352 KB Output is correct
10 Correct 47 ms 47352 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47356 KB Output is correct
2 Correct 44 ms 47432 KB Output is correct
3 Correct 47 ms 47352 KB Output is correct
4 Correct 45 ms 47352 KB Output is correct
5 Correct 45 ms 47352 KB Output is correct
6 Correct 48 ms 47356 KB Output is correct
7 Correct 48 ms 47416 KB Output is correct
8 Correct 48 ms 47376 KB Output is correct
9 Correct 47 ms 47352 KB Output is correct
10 Correct 47 ms 47352 KB Output is correct
11 Correct 70 ms 47632 KB Output is correct
12 Correct 67 ms 47740 KB Output is correct
13 Correct 64 ms 47864 KB Output is correct
14 Correct 74 ms 47992 KB Output is correct
15 Correct 73 ms 47992 KB Output is correct
16 Correct 69 ms 47864 KB Output is correct
17 Correct 68 ms 47736 KB Output is correct
18 Correct 67 ms 47864 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3023 ms 125048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 56744 KB Output is correct
2 Correct 552 ms 58044 KB Output is correct
3 Correct 614 ms 56212 KB Output is correct
4 Correct 553 ms 56376 KB Output is correct
5 Correct 549 ms 56548 KB Output is correct
6 Correct 522 ms 55336 KB Output is correct
7 Correct 508 ms 55364 KB Output is correct
8 Correct 519 ms 56936 KB Output is correct
9 Correct 440 ms 52336 KB Output is correct
10 Correct 523 ms 56680 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47356 KB Output is correct
2 Correct 44 ms 47432 KB Output is correct
3 Correct 47 ms 47352 KB Output is correct
4 Correct 45 ms 47352 KB Output is correct
5 Correct 45 ms 47352 KB Output is correct
6 Correct 48 ms 47356 KB Output is correct
7 Correct 48 ms 47416 KB Output is correct
8 Correct 48 ms 47376 KB Output is correct
9 Correct 47 ms 47352 KB Output is correct
10 Correct 47 ms 47352 KB Output is correct
11 Correct 70 ms 47632 KB Output is correct
12 Correct 67 ms 47740 KB Output is correct
13 Correct 64 ms 47864 KB Output is correct
14 Correct 74 ms 47992 KB Output is correct
15 Correct 73 ms 47992 KB Output is correct
16 Correct 69 ms 47864 KB Output is correct
17 Correct 68 ms 47736 KB Output is correct
18 Correct 67 ms 47864 KB Output is correct
19 Correct 1304 ms 72792 KB Output is correct
20 Correct 1358 ms 72736 KB Output is correct
21 Correct 1224 ms 71248 KB Output is correct
22 Correct 1227 ms 71176 KB Output is correct
23 Correct 1219 ms 71152 KB Output is correct
24 Correct 1181 ms 66304 KB Output is correct
25 Correct 1184 ms 66396 KB Output is correct
26 Correct 1204 ms 67028 KB Output is correct
27 Correct 1207 ms 67012 KB Output is correct
28 Correct 1218 ms 67200 KB Output is correct
29 Correct 1234 ms 68068 KB Output is correct
30 Correct 1241 ms 68012 KB Output is correct
31 Correct 1282 ms 68016 KB Output is correct
32 Correct 1233 ms 68112 KB Output is correct
33 Correct 1228 ms 68020 KB Output is correct
34 Correct 1146 ms 65784 KB Output is correct
35 Correct 1133 ms 65648 KB Output is correct
36 Correct 1127 ms 65488 KB Output is correct
37 Correct 1127 ms 65512 KB Output is correct
38 Correct 1159 ms 65660 KB Output is correct
39 Correct 1154 ms 67156 KB Output is correct
40 Correct 1057 ms 63020 KB Output is correct
41 Correct 1154 ms 67084 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47356 KB Output is correct
2 Correct 44 ms 47432 KB Output is correct
3 Correct 47 ms 47352 KB Output is correct
4 Correct 45 ms 47352 KB Output is correct
5 Correct 45 ms 47352 KB Output is correct
6 Correct 48 ms 47356 KB Output is correct
7 Correct 48 ms 47416 KB Output is correct
8 Correct 48 ms 47376 KB Output is correct
9 Correct 47 ms 47352 KB Output is correct
10 Correct 47 ms 47352 KB Output is correct
11 Correct 70 ms 47632 KB Output is correct
12 Correct 67 ms 47740 KB Output is correct
13 Correct 64 ms 47864 KB Output is correct
14 Correct 74 ms 47992 KB Output is correct
15 Correct 73 ms 47992 KB Output is correct
16 Correct 69 ms 47864 KB Output is correct
17 Correct 68 ms 47736 KB Output is correct
18 Correct 67 ms 47864 KB Output is correct
19 Execution timed out 3023 ms 125048 KB Time limit exceeded
20 Halted 0 ms 0 KB -