oj.uz

Submission #558421

# Submission time Handle Problem Language Result Execution time Memory
558421 2022-05-07T09:44:41 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 long long
#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 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(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 86 ms 188108 KB Output is correct
2 Correct 85 ms 188076 KB Output is correct
3 Correct 85 ms 188160 KB Output is correct
4 Correct 96 ms 188280 KB Output is correct
5 Correct 88 ms 188160 KB Output is correct
6 Correct 90 ms 188380 KB Output is correct
7 Correct 90 ms 188400 KB Output is correct
8 Correct 100 ms 188388 KB Output is correct
9 Correct 93 ms 188208 KB Output is correct
10 Correct 86 ms 188224 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 188108 KB Output is correct
2 Correct 85 ms 188076 KB Output is correct
3 Correct 85 ms 188160 KB Output is correct
4 Correct 96 ms 188280 KB Output is correct
5 Correct 88 ms 188160 KB Output is correct
6 Correct 90 ms 188380 KB Output is correct
7 Correct 90 ms 188400 KB Output is correct
8 Correct 100 ms 188388 KB Output is correct
9 Correct 93 ms 188208 KB Output is correct
10 Correct 86 ms 188224 KB Output is correct
11 Correct 151 ms 189132 KB Output is correct
12 Correct 288 ms 191624 KB Output is correct
13 Correct 300 ms 191732 KB Output is correct
14 Correct 456 ms 191812 KB Output is correct
15 Correct 460 ms 191716 KB Output is correct
16 Correct 1631 ms 192004 KB Output is correct
17 Correct 881 ms 191116 KB Output is correct
18 Correct 103 ms 188840 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 325 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 3065 ms 243224 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 188108 KB Output is correct
2 Correct 85 ms 188076 KB Output is correct
3 Correct 85 ms 188160 KB Output is correct
4 Correct 96 ms 188280 KB Output is correct
5 Correct 88 ms 188160 KB Output is correct
6 Correct 90 ms 188380 KB Output is correct
7 Correct 90 ms 188400 KB Output is correct
8 Correct 100 ms 188388 KB Output is correct
9 Correct 93 ms 188208 KB Output is correct
10 Correct 86 ms 188224 KB Output is correct
11 Correct 151 ms 189132 KB Output is correct
12 Correct 288 ms 191624 KB Output is correct
13 Correct 300 ms 191732 KB Output is correct
14 Correct 456 ms 191812 KB Output is correct
15 Correct 460 ms 191716 KB Output is correct
16 Correct 1631 ms 192004 KB Output is correct
17 Correct 881 ms 191116 KB Output is correct
18 Correct 103 ms 188840 KB Output is correct
19 Runtime error 263 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 86 ms 188108 KB Output is correct
2 Correct 85 ms 188076 KB Output is correct
3 Correct 85 ms 188160 KB Output is correct
4 Correct 96 ms 188280 KB Output is correct
5 Correct 88 ms 188160 KB Output is correct
6 Correct 90 ms 188380 KB Output is correct
7 Correct 90 ms 188400 KB Output is correct
8 Correct 100 ms 188388 KB Output is correct
9 Correct 93 ms 188208 KB Output is correct
10 Correct 86 ms 188224 KB Output is correct
11 Correct 151 ms 189132 KB Output is correct
12 Correct 288 ms 191624 KB Output is correct
13 Correct 300 ms 191732 KB Output is correct
14 Correct 456 ms 191812 KB Output is correct
15 Correct 460 ms 191716 KB Output is correct
16 Correct 1631 ms 192004 KB Output is correct
17 Correct 881 ms 191116 KB Output is correct
18 Correct 103 ms 188840 KB Output is correct
19 Runtime error 325 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -