oj.uz

Submission #558585

# Submission time Handle Problem Language Result Execution time Memory
558585 2022-05-07T14:58:30 Z urosk Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
30 / 100
 1506 ms 251784 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;
}
struct node{
    ll lf,rf,ok;
};
node mrg(node a,node b){
    node c;
    if(a.ok==-1) return b;
    if(b.ok==-1) return a;
    c.lf = a.lf;
    c.rf = b.rf;
    c.ok = 0;
    if((a.ok==1)&&(b.ok==1)&&(b.lf>=a.rf)) c.ok = 1;
    return c;
}
node seg[4*maxn];

void init2(ll v,ll tl,ll tr){
    if(tl==tr){
        seg[v].lf = a[tl];
        seg[v].rf = a[tl];
        seg[v].ok = 1;
        return;
    }
    ll mid = (tl+tr)/2;
    init2(2*v,tl,mid);
    init2(2*v+1,mid+1,tr);
    seg[v] = mrg(seg[2*v],seg[2*v+1]);
}
node get2(ll v,ll tl,ll tr,ll l,ll r){
    if(l>r) return {0,0,-1};
    if(tl==l&&tr==r) return seg[v];
    ll mid = (tl+tr)/2;
    return mrg(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).ok<<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

5 2
1 2 3 4 5
1 3 0
2 5 0

5 2
1 3 2 5 4
1 3 0
1 2 0
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 188124 KB Output is correct
2 Correct 86 ms 188108 KB Output is correct
3 Correct 81 ms 188184 KB Output is correct
4 Correct 85 ms 188108 KB Output is correct
5 Correct 89 ms 188228 KB Output is correct
6 Correct 85 ms 188464 KB Output is correct
7 Correct 84 ms 188468 KB Output is correct
8 Correct 88 ms 188364 KB Output is correct
9 Correct 87 ms 188304 KB Output is correct
10 Correct 89 ms 188332 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 188124 KB Output is correct
2 Correct 86 ms 188108 KB Output is correct
3 Correct 81 ms 188184 KB Output is correct
4 Correct 85 ms 188108 KB Output is correct
5 Correct 89 ms 188228 KB Output is correct
6 Correct 85 ms 188464 KB Output is correct
7 Correct 84 ms 188468 KB Output is correct
8 Correct 88 ms 188364 KB Output is correct
9 Correct 87 ms 188304 KB Output is correct
10 Correct 89 ms 188332 KB Output is correct
11 Correct 90 ms 189088 KB Output is correct
12 Correct 100 ms 191652 KB Output is correct
13 Correct 102 ms 191496 KB Output is correct
14 Correct 104 ms 191688 KB Output is correct
15 Correct 103 ms 191588 KB Output is correct
16 Correct 793 ms 191952 KB Output is correct
17 Correct 521 ms 191112 KB Output is correct
18 Correct 87 ms 188768 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1495 ms 238636 KB Output is correct
2 Correct 1492 ms 251600 KB Output is correct
3 Correct 1506 ms 251496 KB Output is correct
4 Correct 1490 ms 251556 KB Output is correct
5 Correct 1478 ms 251784 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 188124 KB Output is correct
2 Correct 86 ms 188108 KB Output is correct
3 Correct 81 ms 188184 KB Output is correct
4 Correct 85 ms 188108 KB Output is correct
5 Correct 89 ms 188228 KB Output is correct
6 Correct 85 ms 188464 KB Output is correct
7 Correct 84 ms 188468 KB Output is correct
8 Correct 88 ms 188364 KB Output is correct
9 Correct 87 ms 188304 KB Output is correct
10 Correct 89 ms 188332 KB Output is correct
11 Correct 90 ms 189088 KB Output is correct
12 Correct 100 ms 191652 KB Output is correct
13 Correct 102 ms 191496 KB Output is correct
14 Correct 104 ms 191688 KB Output is correct
15 Correct 103 ms 191588 KB Output is correct
16 Correct 793 ms 191952 KB Output is correct
17 Correct 521 ms 191112 KB Output is correct
18 Correct 87 ms 188768 KB Output is correct
19 Incorrect 330 ms 202116 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 188124 KB Output is correct
2 Correct 86 ms 188108 KB Output is correct
3 Correct 81 ms 188184 KB Output is correct
4 Correct 85 ms 188108 KB Output is correct
5 Correct 89 ms 188228 KB Output is correct
6 Correct 85 ms 188464 KB Output is correct
7 Correct 84 ms 188468 KB Output is correct
8 Correct 88 ms 188364 KB Output is correct
9 Correct 87 ms 188304 KB Output is correct
10 Correct 89 ms 188332 KB Output is correct
11 Correct 90 ms 189088 KB Output is correct
12 Correct 100 ms 191652 KB Output is correct
13 Correct 102 ms 191496 KB Output is correct
14 Correct 104 ms 191688 KB Output is correct
15 Correct 103 ms 191588 KB Output is correct
16 Correct 793 ms 191952 KB Output is correct
17 Correct 521 ms 191112 KB Output is correct
18 Correct 87 ms 188768 KB Output is correct
19 Correct 1495 ms 238636 KB Output is correct
20 Correct 1492 ms 251600 KB Output is correct
21 Correct 1506 ms 251496 KB Output is correct
22 Correct 1490 ms 251556 KB Output is correct
23 Correct 1478 ms 251784 KB Output is correct
24 Incorrect 196 ms 193848 KB Output isn't correct
25 Halted 0 ms 0 KB -