oj.uz

Submission #558422

# Submission time Handle Problem Language Result Execution time Memory
558422 2022-05-07T09:45:54 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 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 89 ms 188144 KB Output is correct
2 Correct 83 ms 188176 KB Output is correct
3 Correct 91 ms 188224 KB Output is correct
4 Correct 86 ms 188148 KB Output is correct
5 Correct 87 ms 188240 KB Output is correct
6 Correct 89 ms 188424 KB Output is correct
7 Correct 87 ms 188428 KB Output is correct
8 Correct 101 ms 188460 KB Output is correct
9 Correct 104 ms 188264 KB Output is correct
10 Correct 87 ms 188236 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 188144 KB Output is correct
2 Correct 83 ms 188176 KB Output is correct
3 Correct 91 ms 188224 KB Output is correct
4 Correct 86 ms 188148 KB Output is correct
5 Correct 87 ms 188240 KB Output is correct
6 Correct 89 ms 188424 KB Output is correct
7 Correct 87 ms 188428 KB Output is correct
8 Correct 101 ms 188460 KB Output is correct
9 Correct 104 ms 188264 KB Output is correct
10 Correct 87 ms 188236 KB Output is correct
11 Correct 151 ms 189124 KB Output is correct
12 Correct 294 ms 191596 KB Output is correct
13 Correct 291 ms 191492 KB Output is correct
14 Correct 470 ms 191800 KB Output is correct
15 Correct 471 ms 191716 KB Output is correct
16 Correct 1595 ms 191828 KB Output is correct
17 Correct 909 ms 191096 KB Output is correct
18 Correct 91 ms 188712 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 188144 KB Output is correct
2 Correct 83 ms 188176 KB Output is correct
3 Correct 91 ms 188224 KB Output is correct
4 Correct 86 ms 188148 KB Output is correct
5 Correct 87 ms 188240 KB Output is correct
6 Correct 89 ms 188424 KB Output is correct
7 Correct 87 ms 188428 KB Output is correct
8 Correct 101 ms 188460 KB Output is correct
9 Correct 104 ms 188264 KB Output is correct
10 Correct 87 ms 188236 KB Output is correct
11 Correct 151 ms 189124 KB Output is correct
12 Correct 294 ms 191596 KB Output is correct
13 Correct 291 ms 191492 KB Output is correct
14 Correct 470 ms 191800 KB Output is correct
15 Correct 471 ms 191716 KB Output is correct
16 Correct 1595 ms 191828 KB Output is correct
17 Correct 909 ms 191096 KB Output is correct
18 Correct 91 ms 188712 KB Output is correct
19 Runtime error 247 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 89 ms 188144 KB Output is correct
2 Correct 83 ms 188176 KB Output is correct
3 Correct 91 ms 188224 KB Output is correct
4 Correct 86 ms 188148 KB Output is correct
5 Correct 87 ms 188240 KB Output is correct
6 Correct 89 ms 188424 KB Output is correct
7 Correct 87 ms 188428 KB Output is correct
8 Correct 101 ms 188460 KB Output is correct
9 Correct 104 ms 188264 KB Output is correct
10 Correct 87 ms 188236 KB Output is correct
11 Correct 151 ms 189124 KB Output is correct
12 Correct 294 ms 191596 KB Output is correct
13 Correct 291 ms 191492 KB Output is correct
14 Correct 470 ms 191800 KB Output is correct
15 Correct 471 ms 191716 KB Output is correct
16 Correct 1595 ms 191828 KB Output is correct
17 Correct 909 ms 191096 KB Output is correct
18 Correct 91 ms 188712 KB Output is correct
19 Runtime error 324 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -