oj.uz

Submission #993084

# Submission time Handle Problem Language Result Execution time Memory
993084 2024-06-05T09:59:41 Z serkanrashid Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 571 ms 92244 KB 
#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;
    for(int i = r; i >= l; i = bigidx[i])
    {
        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;

        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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 571 ms 92244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 15448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -