Submission #692536

#	Time	Username	Problem	Language	Result	Execution time	Memory
692536		Mer123haba456	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	34 / 100	716 ms	262144 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef long double ld;
#define N lli(2e6)
#define MOD lli(1e9 + 7)
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0);
#define heps(v) v.begin(),v.end()
typedef vector<lli> vlli;
typedef pair<lli,lli> plli;
typedef pair<lli,plli> pplli;
typedef pair<plli,plli> ppplli;
typedef vector<plli> vplli;
typedef vector<pplli> vpplli;
typedef map<lli,lli> mlli;
typedef set<lli> slli;

lli t,n,m,k;

string str;

lli seg[N];
plli enbseg[N];
slli karseg[N];

vlli vect;

plli operator+(plli a,lli b){
    if(b > a.first){
        a.second = a.first;
        a.first = b;
    }else if(b > a.second && b != a.first){
        a.second = b;
    }
    return a;
}

plli operator+(plli a,plli b){
    a = a + b.first;
    a = a + b.second;
    return a;
}

bool operator>(plli a,plli b){
    lli sua = (a.second == -1 ? 0 : a.first + a.second);
    lli sub = (b.second == -1 ? 0 : b.first + b.second);
    return sua > sub;
}

void yap(lli v,lli l,lli r){
    if(l == r){
        plli su = {-1,-1};
        seg[v] = vect[l];
        enbseg[v] = {vect[l],-1};
        karseg[v].insert(vect[l]);
        return;
    }
    lli m = (l+r)/2;
    yap(2*v,l,m);
    yap(2*v+1,m+1,r);
    seg[v] = max(seg[2*v], seg[2*v+1]);
    enbseg[v] = enbseg[2*v];
    if(enbseg[2*v+1] > enbseg[2*v])
        enbseg[v] = enbseg[2*v+1];
    plli tmp = {seg[2*v],-1};
    auto de = karseg[2*v+1].lower_bound(seg[2*v]);
    if(de != karseg[2*v+1].begin()){
        de--;
        tmp.second = *de;
    }
    if(tmp > enbseg[v])
        enbseg[v] = tmp;
    for(auto it = karseg[2*v].begin();it!=karseg[2*v].end();it++)
        karseg[v].insert(*it);
    for(auto it = karseg[2*v+1].begin();it!=karseg[2*v+1].end();it++)
        karseg[v].insert(*it);
}

ppplli getir(lli v,lli l,lli r,lli list,lli rist,lli ist){
    if(list<= l && r <= rist){
        auto de = karseg[v].lower_bound(ist);
        lli dond = -1;
        if(de != karseg[v].begin()){
            de--;
            dond = *de;
        }
        ppplli su = {enbseg[v],{max(seg[v],ist),dond}};
        return su;
    }
    lli m = (l+r)/2;
    if(rist<=m)
        return getir(2*v,l,m,list,rist,ist);
    else if(list > m)
        return getir(2*v+1,m+1,r,list,rist,ist);
    else{
        ppplli su = getir(2*v,l,m,list,rist,ist); 
        plli ilk = {-1,-1};
        if(su.second.second < ist)
            ilk = {ist,su.second.second};
        if(su.first > ilk)
            ilk = su.first;
        ppplli sui = getir(2*v+1,m+1,r,list,rist, su.second.first);
        plli iki = {-1,-1};
        if(sui.second.second < su.second.first)
            iki = {su.second.first, sui.second.second};
        if(sui.first > iki)
            iki = sui.first;
        if(iki > ilk)
            ilk = iki;
        ppplli dond = {ilk, {max(su.second.first,sui.second.first),max(su.second.second,sui.second.second)}};
        return dond;
    }
}

int main(){
    fast_io
    /*slli se = {0,5,7,8};
    auto it = se.lower_bound(0);
    cout << (it == se.begin()) << endl;*/
    cin >> n >> t;
    for(lli i = 0;i<n;i++){
        cin >> k;
        vect.push_back(k);
    }
    yap(1,0,n-1);
    while(t--){
        lli a,b,c;
        cin >> a >> b >> c;
        a--;
        b--;
        plli su = getir(1,0,n-1,a,b,-1).first;
        if(su.second == -1 || su.first == -1 || (c >= su.first + su.second))
            cout << "1" << endl;
        else
            cout << "0" << endl;
    }
}

Compilation message (stderr)

sortbooks.cpp: In function 'void yap(lli, lli, lli)':
sortbooks.cpp:52:14: warning: variable 'su' set but not used [-Wunused-but-set-variable]
   52 |         plli su = {-1,-1};
      |              ^~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 13
• Subtask 4: 17 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23