oj.uz

Submission #558461

# Submission time Handle Problem Language Result Execution time Memory
558461 2022-05-07T11:50:00 Z urosk Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
17 / 100
 861 ms 262144 KB 
// __builtin_popcount(x)
// __builtin_popcountll(x)
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll int
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;
#define maxn 1000005
ll n,q;
ll a[maxn];
set<ll> t[4*maxn];
ll val[4*maxn];
ll mood;
bool moe = 1;
void init(ll v,ll tl,ll tr){
    if(tl==tr){
        t[v].insert(a[tl]);
        return;
    }
    ll mid = (tl+tr)/2;
    init(2*v,tl,mid);
    init(2*v+1,mid+1,tr);
    auto it = t[2*v].end(); it--;
    ll x = *it;
    it = t[2*v+1].lower_bound(x);
    if(it==t[2*v+1].begin()){
        val[v] = 0;
    }else{
        it--;
        val[v] = x + *it;
    }
    val[v] = max(val[v],max(val[2*v],val[2*v+1]));
    //here;
    //cerr<<tl<< " "<<tr<<" "<<val[v]<<" "<<*it<<endl;
    for(ll i = tl;i<=tr;i++) t[v].insert(a[i]);
}
set<ll> get(ll v,ll tl,ll tr,ll l,ll r){
    if(l>r) return {};
    if(tl==l&&tr==r){
        if(val[v]>mood){
            moe = 0;
             return {};
        }
        return t[v];
    }
    ll mid = (tl+tr)/2;
    set<ll> lf = get(2*v,tl,mid,l,min(mid,r));
    set<ll> rf = get(2*v+1,mid+1,tr,max(mid+1,l),r);
    if(moe==0) return {};
    if(sz(lf)==0) return rf;
    if(sz(rf)==0) return lf;
    auto it = lf.end();
    it--;
    ll x = *it;
    it = rf.lower_bound(x);
    if(it==rf.begin()){
        for(ll x : lf) rf.insert(x);
        return rf;
    }
    it--;
    if(x+*it>mood){
        moe = 0;
        return {};
    }
    for(ll x : lf) rf.insert(x);
    return rf;
}
ll seg[4*maxn];
void init2(ll v,ll tl,ll tr){
    if(tl==tr){
        seg[v] = a[tl];
        return;
    }
    ll mid = (tl+tr)/2;
    init2(2*v,tl,mid);
    init2(2*v+1,mid+1,tr);
    seg[v] = max(seg[2*v+1],seg[2*v+1]);
}
ll get2(ll v,ll tl,ll tr,ll l,ll r){
    if(l>r) return 0;
    if(tl==l&&tr==r) return seg[v];
    ll mid = (tl+tr)/2;
    return max(get2(2*v,tl,mid,l,min(mid,r)),get2(2*v+1,mid+1,tr,max(mid+1,l),r));
}
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> q;
    for(ll i = 1;i<=n;i++) cin >> a[i];
    if(n>5000){
        init(1,1,n);
        while(q--){
            ll l,r; cin >> l >> r >> mood;
            cout<<(get2(1,1,n,l,r)<=mood)<<endl;
        }
        return 0;
    }
    init(1,1,n);
    while(q--){
        ll l,r; cin >> l >> r >> mood;
        moe = 1;
        get(1,1,n,l,r);
        cout<<moe<<endl;
    }
	return 0;
}
/*
4 1
1 2 1 1
1 4 1
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 188188 KB Output is correct
2 Correct 86 ms 188120 KB Output is correct
3 Correct 89 ms 188232 KB Output is correct
4 Correct 91 ms 188176 KB Output is correct
5 Correct 85 ms 188248 KB Output is correct
6 Correct 88 ms 188436 KB Output is correct
7 Correct 87 ms 188432 KB Output is correct
8 Correct 93 ms 188412 KB Output is correct
9 Correct 89 ms 188264 KB Output is correct
10 Correct 115 ms 188164 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 188188 KB Output is correct
2 Correct 86 ms 188120 KB Output is correct
3 Correct 89 ms 188232 KB Output is correct
4 Correct 91 ms 188176 KB Output is correct
5 Correct 85 ms 188248 KB Output is correct
6 Correct 88 ms 188436 KB Output is correct
7 Correct 87 ms 188432 KB Output is correct
8 Correct 93 ms 188412 KB Output is correct
9 Correct 89 ms 188264 KB Output is correct
10 Correct 115 ms 188164 KB Output is correct
11 Correct 93 ms 189112 KB Output is correct
12 Correct 101 ms 191628 KB Output is correct
13 Correct 110 ms 191468 KB Output is correct
14 Correct 109 ms 191704 KB Output is correct
15 Correct 110 ms 191608 KB Output is correct
16 Correct 861 ms 191844 KB Output is correct
17 Correct 549 ms 191116 KB Output is correct
18 Correct 100 ms 188696 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 322 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 348 ms 243672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 188188 KB Output is correct
2 Correct 86 ms 188120 KB Output is correct
3 Correct 89 ms 188232 KB Output is correct
4 Correct 91 ms 188176 KB Output is correct
5 Correct 85 ms 188248 KB Output is correct
6 Correct 88 ms 188436 KB Output is correct
7 Correct 87 ms 188432 KB Output is correct
8 Correct 93 ms 188412 KB Output is correct
9 Correct 89 ms 188264 KB Output is correct
10 Correct 115 ms 188164 KB Output is correct
11 Correct 93 ms 189112 KB Output is correct
12 Correct 101 ms 191628 KB Output is correct
13 Correct 110 ms 191468 KB Output is correct
14 Correct 109 ms 191704 KB Output is correct
15 Correct 110 ms 191608 KB Output is correct
16 Correct 861 ms 191844 KB Output is correct
17 Correct 549 ms 191116 KB Output is correct
18 Correct 100 ms 188696 KB Output is correct
19 Runtime error 256 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 188188 KB Output is correct
2 Correct 86 ms 188120 KB Output is correct
3 Correct 89 ms 188232 KB Output is correct
4 Correct 91 ms 188176 KB Output is correct
5 Correct 85 ms 188248 KB Output is correct
6 Correct 88 ms 188436 KB Output is correct
7 Correct 87 ms 188432 KB Output is correct
8 Correct 93 ms 188412 KB Output is correct
9 Correct 89 ms 188264 KB Output is correct
10 Correct 115 ms 188164 KB Output is correct
11 Correct 93 ms 189112 KB Output is correct
12 Correct 101 ms 191628 KB Output is correct
13 Correct 110 ms 191468 KB Output is correct
14 Correct 109 ms 191704 KB Output is correct
15 Correct 110 ms 191608 KB Output is correct
16 Correct 861 ms 191844 KB Output is correct
17 Correct 549 ms 191116 KB Output is correct
18 Correct 100 ms 188696 KB Output is correct
19 Runtime error 322 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -