Submission #993092

#	Time	Username	Problem	Language	Result	Execution time	Memory
993092		serkanrashid	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	559 ms	92444 KiB

sortbooks

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

const int maxn = 1e6+5;

int n,m;
int w[maxn],bigidx[maxn];
int what[maxn],jump[maxn][20];

void pre()
{
    int last = 0;
    for(int j = 0; j <= 20; j++)
    {
        int gr = min(n,(1<<(j+1)));
        for(int i = last + 1; i <= gr; i++) what[i] = j;
        last = gr;
    }
    for(int i = 1; i <= n; i++) jump[i][0] = w[i];
    for(int j = 1; j <= 20; j++)
    {
        for(int i = 1; i <= n; i++)
        {
            jump[i][j] = max(jump[i][j-1],jump[jump[i][j-1]+1][j-1]);
        }
    }
}

int query(int l, int r)
{
    if(l>r) return -1;
    int step = what[r-l+1];
    return max(jump[l][step],jump[r-(1<<step)+1][step]);
}

bool check(int l, int r, int k)
{
    int maxch,razmqna,old = r;
    maxch = razmqna = 0;
    bool f = false;
    for(int i = r; i >= l; i = (f? i-1 : bigidx[i]))
    {
        f = false;
        maxch = w[i];
        int pom = query(i+1,old-1);
        if(i!=old&&w[i]>w[old]) pom = max(pom,w[old]);
        if(pom!=-1) maxch += pom;
        else f = true;

        razmqna = max(razmqna,maxch);
        old = i;
    }
    return k >= razmqna;
}

void read()
{
    cin >> n >> m;

    pre();
    for(int i = 1; i <= n; i++) cin >> w[i];

    w[0] = 1e9+1;
    stack<int>s1;
    s1.push(0);
    for(int i = 1; i <= n; i++)
    {
        while(!s1.empty()&&w[s1.top()]<w[i]) s1.pop();
        bigidx[i] = s1.top();
        s1.push(i);
    }
    int l,r,k;
    for(int i = 1; i <= m; i++)
    {
        cin >> l >> r >> k;
        if(check(l,r,k)) cout << 1 << endl;
        else cout << 0 << endl;
    }
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	read();
return 0;
}

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