oj.uz

Submission #558462

# Submission time Handle Problem Language Result Execution time Memory
558462 2022-05-07T11:50:39 Z urosk Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
17 / 100
 1093 ms 234040 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){
        init2(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 99 ms 188108 KB Output is correct
2 Correct 84 ms 188148 KB Output is correct
3 Correct 83 ms 188220 KB Output is correct
4 Correct 92 ms 188252 KB Output is correct
5 Correct 87 ms 188192 KB Output is correct
6 Correct 92 ms 188332 KB Output is correct
7 Correct 103 ms 188364 KB Output is correct
8 Correct 93 ms 188448 KB Output is correct
9 Correct 87 ms 188212 KB Output is correct
10 Correct 85 ms 188148 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 188108 KB Output is correct
2 Correct 84 ms 188148 KB Output is correct
3 Correct 83 ms 188220 KB Output is correct
4 Correct 92 ms 188252 KB Output is correct
5 Correct 87 ms 188192 KB Output is correct
6 Correct 92 ms 188332 KB Output is correct
7 Correct 103 ms 188364 KB Output is correct
8 Correct 93 ms 188448 KB Output is correct
9 Correct 87 ms 188212 KB Output is correct
10 Correct 85 ms 188148 KB Output is correct
11 Correct 93 ms 189016 KB Output is correct
12 Correct 100 ms 191488 KB Output is correct
13 Correct 115 ms 191320 KB Output is correct
14 Correct 111 ms 191564 KB Output is correct
15 Correct 101 ms 191420 KB Output is correct
16 Correct 843 ms 191692 KB Output is correct
17 Correct 598 ms 191144 KB Output is correct
18 Correct 90 ms 188724 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 188108 KB Output is correct
2 Correct 84 ms 188148 KB Output is correct
3 Correct 83 ms 188220 KB Output is correct
4 Correct 92 ms 188252 KB Output is correct
5 Correct 87 ms 188192 KB Output is correct
6 Correct 92 ms 188332 KB Output is correct
7 Correct 103 ms 188364 KB Output is correct
8 Correct 93 ms 188448 KB Output is correct
9 Correct 87 ms 188212 KB Output is correct
10 Correct 85 ms 188148 KB Output is correct
11 Correct 93 ms 189016 KB Output is correct
12 Correct 100 ms 191488 KB Output is correct
13 Correct 115 ms 191320 KB Output is correct
14 Correct 111 ms 191564 KB Output is correct
15 Correct 101 ms 191420 KB Output is correct
16 Correct 843 ms 191692 KB Output is correct
17 Correct 598 ms 191144 KB Output is correct
18 Correct 90 ms 188724 KB Output is correct
19 Incorrect 282 ms 197968 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 188108 KB Output is correct
2 Correct 84 ms 188148 KB Output is correct
3 Correct 83 ms 188220 KB Output is correct
4 Correct 92 ms 188252 KB Output is correct
5 Correct 87 ms 188192 KB Output is correct
6 Correct 92 ms 188332 KB Output is correct
7 Correct 103 ms 188364 KB Output is correct
8 Correct 93 ms 188448 KB Output is correct
9 Correct 87 ms 188212 KB Output is correct
10 Correct 85 ms 188148 KB Output is correct
11 Correct 93 ms 189016 KB Output is correct
12 Correct 100 ms 191488 KB Output is correct
13 Correct 115 ms 191320 KB Output is correct
14 Correct 111 ms 191564 KB Output is correct
15 Correct 101 ms 191420 KB Output is correct
16 Correct 843 ms 191692 KB Output is correct
17 Correct 598 ms 191144 KB Output is correct
18 Correct 90 ms 188724 KB Output is correct
19 Incorrect 1093 ms 234040 KB Output isn't correct
20 Halted 0 ms 0 KB -