Submission #1156524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156524		Muhammad_Aneeq	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	1373 ms	98232 KiB

sortbooks

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
#include <vector>
#warning check the output
using namespace std;
int const N=1e6+10;
int fen[N]={};
int w[N]={};
bool ans[N]={};
vector<vector<int>>qu[N]={};
void add(int i,int val)
{
    i++;
    while (i>0)
    {
        fen[i]=max(fen[i],val);
        i-=(i&(-i));
    }
}
int get(int i)
{
    i++;
    int ans=0;
    while (i<N)
    {
        ans=max(ans,fen[i]);
        i+=(i&(-i));
    }
    return ans;
}
inline void solve()
{
    int n,m;
    cin>>n>>m;
    for (int i=0;i<n;i++)
        cin>>w[i];
    for (int i=0;i<m;i++)
    {
        int l,r,k;
        cin>>l>>r>>k;
        qu[r].push_back({l,k,i});
    }
    vector<int>in;
    for (int i=0;i<n;i++)
    {
        while (in.size()&&w[in.back()]<=w[i])
            in.pop_back();
        if (in.size())
            add(in.back(),w[in.back()]+w[i]);
        for (auto j:qu[i])
            ans[j[2]]=(get(j[0])<=j[1]);
        in.push_back(i);
    }
    for (int i=0;i<m;i++)
        cout<<ans[i]<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

Compilation message (stderr)

sortbooks.cpp:9:2: warning: #warning check the output [-Wcpp]
    9 | #warning check the output
      |  ^~~~~~~

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