oj.uz

Submission #151549

# Submission time Handle Problem Language Result Execution time Memory
151549 2019-09-03T14:15:09 Z andrew Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 29924 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 int ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 1e6 + 200;
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) >> 1;
    if(pos <= tm) upd(v << 1, tl, tm, pos, val);
    else upd(v << 1 | 1, tm + 1, tr, pos, val);
    t[v] = max(t[v << 1], t[v << 1 | 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) >> 1;
    return max(get(v << 1, tl, tm, l, min(r, tm)), get(v << 1 | 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 376 KB Output is correct
2 Correct 2 ms 380 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 380 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 376 KB Output is correct
2 Correct 2 ms 380 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 380 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 376 KB Output is correct
12 Correct 12 ms 504 KB Output is correct
13 Correct 12 ms 504 KB Output is correct
14 Correct 16 ms 504 KB Output is correct
15 Correct 16 ms 504 KB Output is correct
16 Correct 13 ms 508 KB Output is correct
17 Correct 11 ms 504 KB Output is correct
18 Correct 11 ms 632 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 4128 KB Output is correct
2 Correct 242 ms 4208 KB Output is correct
3 Correct 226 ms 3872 KB Output is correct
4 Correct 236 ms 3948 KB Output is correct
5 Correct 226 ms 3924 KB Output is correct
6 Correct 206 ms 3948 KB Output is correct
7 Correct 205 ms 4016 KB Output is correct
8 Correct 199 ms 4276 KB Output is correct
9 Correct 143 ms 2624 KB Output is correct
10 Correct 197 ms 3992 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 380 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 380 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 376 KB Output is correct
12 Correct 12 ms 504 KB Output is correct
13 Correct 12 ms 504 KB Output is correct
14 Correct 16 ms 504 KB Output is correct
15 Correct 16 ms 504 KB Output is correct
16 Correct 13 ms 508 KB Output is correct
17 Correct 11 ms 504 KB Output is correct
18 Correct 11 ms 632 KB Output is correct
19 Correct 650 ms 7600 KB Output is correct
20 Correct 643 ms 7732 KB Output is correct
21 Correct 616 ms 7628 KB Output is correct
22 Correct 620 ms 7860 KB Output is correct
23 Correct 614 ms 7796 KB Output is correct
24 Correct 598 ms 7164 KB Output is correct
25 Correct 586 ms 7288 KB Output is correct
26 Correct 612 ms 7292 KB Output is correct
27 Correct 615 ms 7380 KB Output is correct
28 Correct 647 ms 7368 KB Output is correct
29 Correct 638 ms 7516 KB Output is correct
30 Correct 621 ms 7404 KB Output is correct
31 Correct 621 ms 7240 KB Output is correct
32 Correct 623 ms 7228 KB Output is correct
33 Correct 625 ms 7404 KB Output is correct
34 Correct 579 ms 7268 KB Output is correct
35 Correct 576 ms 7452 KB Output is correct
36 Correct 576 ms 7288 KB Output is correct
37 Correct 564 ms 7352 KB Output is correct
38 Correct 605 ms 7232 KB Output is correct
39 Correct 521 ms 7916 KB Output is correct
40 Correct 446 ms 6668 KB Output is correct
41 Correct 524 ms 7496 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 380 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 380 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 376 KB Output is correct
12 Correct 12 ms 504 KB Output is correct
13 Correct 12 ms 504 KB Output is correct
14 Correct 16 ms 504 KB Output is correct
15 Correct 16 ms 504 KB Output is correct
16 Correct 13 ms 508 KB Output is correct
17 Correct 11 ms 504 KB Output is correct
18 Correct 11 ms 632 KB Output is correct
19 Execution timed out 3004 ms 29924 KB Time limit exceeded
20 Halted 0 ms 0 KB -