Submission #707135

#	Time	Username	Problem	Language	Result	Execution time	Memory
707135		Karuk	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2965 ms	222904 KiB

sortbooks

#include<bits/stdc++.h>///3:27- func start///3:41 end
using namespace std;
vector<vector<int>>st;
int score[4000000];
int k=1;
vector<int>ind;
void push(int from,int to,int cur=1,int beg=0,int en=k-1) {
    if(from>en || to<beg)return;
    if(from<=beg && en<=to){ind.push_back(cur);return;}
    int mid=(beg+en)/2;
    push(from,to,cur*2,beg,mid);
    push(from,to,cur*2+1,mid+1,en);
}
int combine(int i,int j) {
    if(st[j].size()==0 || st[i].size()==0)return score[i];
    int mx=st[i].back();
    int ans=max(score[i],score[j]);
    int ind=lower_bound(st[j].begin(),st[j].end(),mx)-st[j].begin();
    ind--;
    if(ind>=0)ans=max(ans,mx+st[j][ind]);
    return ans;
}
int maxw(int l,int r) {
    ind.clear();
    push(l,r);
    int ans=score[ind.back()];
    int maxind=0;
    for(int i=1;i<ind.size();i++) {
        ans=max(ans,combine(ind[maxind],ind[i]));
        if(st[ind[i]].back()>st[ind[maxind]].back())maxind=i;
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;
    int a[n];
    for(int i=0;i<n;i++)cin>>a[i];
    while(k<n){k<<=1;}
    st.resize(k*2+1);
    for(int i=0;i<n;i++)st[i+k].push_back(a[i]);
    for(int i=k-1;i>0;i--) {
        int p1=0,p2=0;
        while(p1<st[i*2].size() && p2<st[i*2+1].size()) {
            if(st[i*2][p1]<st[i*2+1][p2]) {
                st[i].push_back(st[i*2][p1]);
                p1++;
            } else {
                st[i].push_back(st[i*2+1][p2]);
                p2++;
            }
        }
        while(p1<st[i*2].size()) {
            st[i].push_back(st[i*2][p1]);
            p1++;
        }
        while(p2<st[i*2+1].size()) {
            st[i].push_back(st[i*2+1][p2]);
            p2++;
        }
        score[i]=combine(2*i,2*i+1);
    }
    for(int i=0;i<m;i++) {
        int l,r,w;cin>>l>>r>>w;
        l--;r--;
        int as=maxw(l,r);
        if(as<=w)cout<<1<<'\n';
        else cout<<0<<'\n';
    }
    return 0;
}
/**
5 6
3 2 9 8 1
*/

Compilation message (stderr)

sortbooks.cpp: In function 'int maxw(int, int)':
sortbooks.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=1;i<ind.size();i++) {
      |                 ~^~~~~~~~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:44:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         while(p1<st[i*2].size() && p2<st[i*2+1].size()) {
      |               ~~^~~~~~~~~~~~~~~
sortbooks.cpp:44:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         while(p1<st[i*2].size() && p2<st[i*2+1].size()) {
      |                                    ~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         while(p1<st[i*2].size()) {
      |               ~~^~~~~~~~~~~~~~~
sortbooks.cpp:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         while(p2<st[i*2+1].size()) {
      |               ~~^~~~~~~~~~~~~~~~~

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