답안 #558607

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
558607	2022-05-07T15:23:15 Z	urosk	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	13 / 100	2137 ms	83044 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 neutral;
node get2(ll v,ll tl,ll tr,ll l,ll r){
    if(l>r) return neutral;
    if(tl==l&&tr==r) return seg[v];
    ll mid = (tl+tr)/2;
    node ans =  mrg(get2(2*v,tl,mid,l,min(mid,r)),get2(2*v+1,mid+1,tr,max(mid+1,l),r));
    //cerr<<tl<< " "<<tr<< " "<<ans.lf<< " "<<ans.rf<< " "<<ans.c<<" "<<ans.ok<<endl;
    return ans;
}
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);
	neutral.ok = -1;
    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++;
        }
        node rez = get2(1,1,n,l,r);
        //cerr<<rez.lf<< " "<<rez.rf<< " "<<rez.ok<<endl;
        ans[id] = rez.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 1
1 3 2 5 4
2 5 3

*/

Subtask #1
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 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

#	결과	실행 시간	메모리	Grader output
1	Correct	3 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

#	결과	실행 시간	메모리	Grader output
1	Correct	2095 ms	83004 KB	Output is correct
2	Correct	2137 ms	82936 KB	Output is correct
3	Correct	2019 ms	83000 KB	Output is correct
4	Correct	1810 ms	83044 KB	Output is correct
5	Correct	1862 ms	83032 KB	Output is correct