Submission #558600

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
558600	2022-05-07T15:14:41 Z	urosk	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	13 / 100	1797 ms	83344 KB

sortbooks

// __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];
struct upit{
    ll l,r,mood,id;
};
bool cmp(upit x,upit y){
    return x.mood<y.mood;
}
struct node{
    ll lf,rf,ok,c,mini,maxi;
};
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;
    c.c = 0;
    c.mini = min(a.mini,b.mini);
    c.maxi = max(a.maxi,b.maxi);
    if((a.c==1)&&(b.c==1)) c.c = 1;
    if(c.c==1){
        c.ok = 1;
        c.lf = c.mini;
        c.rf = c.maxi;
        return c;
    }
    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].mini = a[tl];
        seg[v].maxi = 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,0,0,0};
    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));
}
void upd(ll v,ll tl,ll tr,ll i){
    if(tl==tr){
        seg[v].c = 1;
        return;
    }
    ll mid = (tl+tr)/2;
    if(i<=mid) upd(2*v,tl,mid,i);
    else upd(2*v+1,mid+1,tr,i);
    seg[v] = mrg(seg[2*v],seg[2*v+1]);
}
ll ans[maxn];
pll b[maxn];
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];
    for(ll i = 1;i<=n;i++) b[i] = {a[i],i};
    vector<upit> kv;
    for(ll i = 1;i<=q;i++){
        ll l,r,mood; cin >> l >> r >> mood;
        kv.pb({l,r,mood,i});
    }
    init2(1,1,n);
    sort(all(kv),cmp);
    sort(b+1,b+n+1);
    ll j = 1;
    for(upit p : kv){
        ll l = p.l;
        ll r = p.r;
        ll m = p.mood;
        ll id = p.id;
        while(j<=n&&b[j].fi<=m){
            upd(1,1,n,b[j].sc);
            j++;
        }
        ans[id] = get2(1,1,n,l,r).ok;
    }
    for(ll i = 1;i<=q;i++) cout<<ans[i]<<endl;
	return 0;
}
/*
5 2
3 5 1 8 2
1 3 6
2 5 3

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
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Incorrect	1 ms	340 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Incorrect	1 ms	340 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1797 ms	83052 KB	Output is correct
2	Correct	1729 ms	83072 KB	Output is correct
3	Correct	1730 ms	82976 KB	Output is correct
4	Correct	1737 ms	83344 KB	Output is correct
5	Correct	1642 ms	83256 KB	Output is correct