oj.uz

Submission #151537

# Submission time Handle Problem Language Result Execution time Memory
151537 2019-09-03T14:02:55 Z andrew Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 75572 KB 
#include <bits/stdc++.h>

#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 sqr(x) (x)*(x)
#define pw(x) (1ll << x)

using namespace std;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 1e6 + 5;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

template <typename T> void vout(T s){cout << s << endl;exit(0);}
vector<pair<ll, ll> > v;
pair<pair<ll, ll>, ll> b[N];
vector<ll> q;
ll t[4 * N],a[N],n,Q,limit,l,r,x,k,ans[N];
void upd(ll v,ll tl,ll tr,ll pos,ll val)
{
    if(tl == tr)
    {
        t[v] = val + a[tl];
        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));
}
void make(ll l,ll r)
{
    for(int i = r; i >= l; i--)
    {
        ll x = a[i],pos;
        while(!v.empty() && x > v.back().fi)
        {
            pos = v.back().se;
            upd(1, 1, n, pos, x);
            v.pop_back();
        }
        v.push_back({x, i});
    }
}
bool comp(ll i,ll j)
{
    return b[i].fi.fi > b[j].fi.fi;
}
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];
    limit = n;
    for(int i = 1; i <= Q; i++)
    {
        cin>>l>>r>>x;
        b[i] = {{l, r}, x};
        q.push_back(i);
    }
    sort(all(q), comp);
    for(auto i : q)
    {
        l = b[i].fi.fi;
        r = b[i].fi.se;
        k = b[i].se;
        if(limit >= l)
        {
            make(l, limit);
            limit = l - 1;
        }
        x = get(1, 1, n, l, r);
        ans[i] = (x <= k);
    }
    for(int i = 1; i <= Q; i++) cout<<ans[i]<<"\n";
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 404 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 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 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 404 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 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 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 9 ms 504 KB Output is correct
12 Correct 12 ms 632 KB Output is correct
13 Correct 13 ms 632 KB Output is correct
14 Correct 17 ms 760 KB Output is correct
15 Correct 17 ms 760 KB Output is correct
16 Correct 13 ms 760 KB Output is correct
17 Correct 12 ms 760 KB Output is correct
18 Correct 11 ms 888 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 7388 KB Output is correct
2 Correct 248 ms 7356 KB Output is correct
3 Correct 253 ms 7372 KB Output is correct
4 Correct 248 ms 7360 KB Output is correct
5 Correct 246 ms 7256 KB Output is correct
6 Correct 229 ms 7016 KB Output is correct
7 Correct 229 ms 7048 KB Output is correct
8 Correct 219 ms 7580 KB Output is correct
9 Correct 152 ms 4588 KB Output is correct
10 Correct 219 ms 7400 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 404 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 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 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 9 ms 504 KB Output is correct
12 Correct 12 ms 632 KB Output is correct
13 Correct 13 ms 632 KB Output is correct
14 Correct 17 ms 760 KB Output is correct
15 Correct 17 ms 760 KB Output is correct
16 Correct 13 ms 760 KB Output is correct
17 Correct 12 ms 760 KB Output is correct
18 Correct 11 ms 888 KB Output is correct
19 Correct 692 ms 14440 KB Output is correct
20 Correct 703 ms 21316 KB Output is correct
21 Correct 658 ms 20836 KB Output is correct
22 Correct 690 ms 20772 KB Output is correct
23 Correct 661 ms 20948 KB Output is correct
24 Correct 625 ms 19916 KB Output is correct
25 Correct 626 ms 19856 KB Output is correct
26 Correct 654 ms 20712 KB Output is correct
27 Correct 652 ms 20444 KB Output is correct
28 Correct 660 ms 20600 KB Output is correct
29 Correct 665 ms 20788 KB Output is correct
30 Correct 660 ms 20680 KB Output is correct
31 Correct 659 ms 20616 KB Output is correct
32 Correct 665 ms 20708 KB Output is correct
33 Correct 663 ms 20808 KB Output is correct
34 Correct 613 ms 19704 KB Output is correct
35 Correct 620 ms 19796 KB Output is correct
36 Correct 609 ms 19780 KB Output is correct
37 Correct 602 ms 19420 KB Output is correct
38 Correct 635 ms 19764 KB Output is correct
39 Correct 564 ms 20576 KB Output is correct
40 Correct 489 ms 17416 KB Output is correct
41 Correct 525 ms 18752 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 404 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 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 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 9 ms 504 KB Output is correct
12 Correct 12 ms 632 KB Output is correct
13 Correct 13 ms 632 KB Output is correct
14 Correct 17 ms 760 KB Output is correct
15 Correct 17 ms 760 KB Output is correct
16 Correct 13 ms 760 KB Output is correct
17 Correct 12 ms 760 KB Output is correct
18 Correct 11 ms 888 KB Output is correct
19 Execution timed out 3044 ms 75572 KB Time limit exceeded
20 Halted 0 ms 0 KB -