Submission #286907

#	Time	Username	Problem	Language	Result	Execution time	Memory
286907		tqbfjotld	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2056 ms	129588 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

struct node{
int s,e,v;
node *l,*r;
node (int _s, int _e){
    s = _s; e = _e;
    if (s!=e){
        l = new node(s,(s+e)/2);
        r = new node((s+e)/2+1,e);
    }
    v = -1;
}
void upd(int pos, int val){
    if (s==e) {v = max(v,val);return;}
    if (pos<=(s+e)/2) l->upd(pos,val);
    else r->upd(pos,val);
    v = max(l->v,r->v);
}
int que(int a, int b){
    if (a<=s && e<=b) return v;
    if (b<=(s+e)/2) return l->que(a,b);
    if (a>(s+e)/2) return r->que(a,b);
    return max(l->que(a,b),r->que(a,b));
}
}*root;

stack<int> thing;
int val[1000005];
int ans[1000005];
vector<pair<pair<int,int>,pair<int,int> > > qu;
vector<pair<int,int> > things;

bool cmp(pair<int,int> a, pair<int,int> b){
    if (a.second==b.second) return a.first<b.first;
    return a.second<b.second;
}

bool cmp2(pair<pair<int,int>,pair<int,int> > a, pair<pair<int,int>,pair<int,int> >b){
    return cmp(a.first,b.first);
}

void input(int &a){
    a = 0;
   char ch = ' ';
    while (ch<'0' || ch>'9'){
        ch = getchar();
    }
    while (ch>='0' && ch<='9'){
        a = (a<<3) + (a<<1) + ch - '0';
        ch = getchar();
    }
}

int main(){
    int n,m;
    input(n);
    input(m);
    for (int x = 0; x<n; x++){
        input(val[x]);
    }
    for (int x = 0; x<n; x++){
        while ((!thing.empty()) && val[thing.top()]<=val[x]){
            thing.pop();
        }
        if (!thing.empty()){
            things.push_back({thing.top(),x});
        }
        thing.push(x);
    }
    sort(things.begin(),things.end(),cmp);
    root = new node(0,n);
    for (int T = 0; T<m; T++){
        int a,b,c;
        input(a); input(b); input(c);
        a--;b--;
        qu.push_back({{a,b},{c,T}});
    }
    sort(qu.begin(),qu.end(),cmp2);
    int c = 0;
    for (auto&x:qu){
        while (c!=things.size() && x.first.second>=things[c].second){
            int v = root->que(things[c].first,things[c].first);
            if (v<val[things[c].first]+val[things[c].second]){
                root->upd(things[c].first,val[things[c].first]+val[things[c].second]);
            }
            c++;
        }
        ans[x.second.second] = root->que(x.first.first,x.first.second)<=x.second.first;
    }
    for (int x = 0; x<m; x++){
        printf("%d\n",ans[x]);
    }
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:83:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         while (c!=things.size() && x.first.second>=things[c].second){
      |                ~^~~~~~~~~~~~~~~

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