oj.uz

Submission #558428

# Submission time Handle Problem Language Result Execution time Memory
558428 2022-05-07T10:00:16 Z urosk Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
17 / 100
 3000 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;
}
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];
    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 94 ms 188144 KB Output is correct
2 Correct 87 ms 188072 KB Output is correct
3 Correct 92 ms 188236 KB Output is correct
4 Correct 89 ms 188176 KB Output is correct
5 Correct 85 ms 188176 KB Output is correct
6 Correct 92 ms 188456 KB Output is correct
7 Correct 86 ms 188364 KB Output is correct
8 Correct 92 ms 188336 KB Output is correct
9 Correct 90 ms 188200 KB Output is correct
10 Correct 92 ms 188208 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 188144 KB Output is correct
2 Correct 87 ms 188072 KB Output is correct
3 Correct 92 ms 188236 KB Output is correct
4 Correct 89 ms 188176 KB Output is correct
5 Correct 85 ms 188176 KB Output is correct
6 Correct 92 ms 188456 KB Output is correct
7 Correct 86 ms 188364 KB Output is correct
8 Correct 92 ms 188336 KB Output is correct
9 Correct 90 ms 188200 KB Output is correct
10 Correct 92 ms 188208 KB Output is correct
11 Correct 92 ms 188944 KB Output is correct
12 Correct 114 ms 191476 KB Output is correct
13 Correct 110 ms 191436 KB Output is correct
14 Correct 108 ms 191560 KB Output is correct
15 Correct 103 ms 191436 KB Output is correct
16 Correct 772 ms 191736 KB Output is correct
17 Correct 516 ms 191208 KB Output is correct
18 Correct 89 ms 188704 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 343 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 Execution timed out 3078 ms 242448 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 188144 KB Output is correct
2 Correct 87 ms 188072 KB Output is correct
3 Correct 92 ms 188236 KB Output is correct
4 Correct 89 ms 188176 KB Output is correct
5 Correct 85 ms 188176 KB Output is correct
6 Correct 92 ms 188456 KB Output is correct
7 Correct 86 ms 188364 KB Output is correct
8 Correct 92 ms 188336 KB Output is correct
9 Correct 90 ms 188200 KB Output is correct
10 Correct 92 ms 188208 KB Output is correct
11 Correct 92 ms 188944 KB Output is correct
12 Correct 114 ms 191476 KB Output is correct
13 Correct 110 ms 191436 KB Output is correct
14 Correct 108 ms 191560 KB Output is correct
15 Correct 103 ms 191436 KB Output is correct
16 Correct 772 ms 191736 KB Output is correct
17 Correct 516 ms 191208 KB Output is correct
18 Correct 89 ms 188704 KB Output is correct
19 Runtime error 249 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 94 ms 188144 KB Output is correct
2 Correct 87 ms 188072 KB Output is correct
3 Correct 92 ms 188236 KB Output is correct
4 Correct 89 ms 188176 KB Output is correct
5 Correct 85 ms 188176 KB Output is correct
6 Correct 92 ms 188456 KB Output is correct
7 Correct 86 ms 188364 KB Output is correct
8 Correct 92 ms 188336 KB Output is correct
9 Correct 90 ms 188200 KB Output is correct
10 Correct 92 ms 188208 KB Output is correct
11 Correct 92 ms 188944 KB Output is correct
12 Correct 114 ms 191476 KB Output is correct
13 Correct 110 ms 191436 KB Output is correct
14 Correct 108 ms 191560 KB Output is correct
15 Correct 103 ms 191436 KB Output is correct
16 Correct 772 ms 191736 KB Output is correct
17 Correct 516 ms 191208 KB Output is correct
18 Correct 89 ms 188704 KB Output is correct
19 Runtime error 343 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -