Submission #779845

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
779845	2023-07-12T01:19:33 Z	khoquennguoiminhthuong	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	495 ms	29692 KB

sortbooks

#include <bits/stdc++.h>

using namespace std;
int n,q;
int a[1000005];
int tree[1000005];
void upd(int id,int val) {
    while(id>0) {
        tree[id]=max(tree[id],val);
        id-=(id&(-id));
    }
}
int get(int id) {
    int maxx=-2e9;
    while(id<=n) {
        maxx=max(maxx,tree[id]);
        id+=(id&(-id));
    }
    return maxx;
}
struct que {
    int l,r,k,id;
} qu[1000005];
bool cmp(que a,que b) {
    return a.r<b.r;
}
int ans[1000005];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1; i<=n; i++)cin>>a[i];
    for(int i=1; i<=q; i++) {
        int l,r,k;
        cin>>l>>r>>k;
        qu[i]= {l,r,k,i};
    }
    for(int i=1;i<=n;i++)tree[i]=-2e9;
    sort(qu+1,qu+q+1,cmp);
    int dd=0;
    stack<int>st;
    for(int i=1; i<=q; i++) {
        while(dd+1<=qu[i].r) {
            dd++;
            while(st.size()&&a[st.top()]<a[dd])st.pop();
            if(st.size()>0){upd(st.top(),a[st.top()]+a[dd]);}
            st.push(dd);
        }
        if(get(qu[i].l)>qu[i].k)ans[qu[i].id]=0;
        else ans[qu[i].id]=1;
    }
    for(int i=1; i<=q; i++)cout<<ans[i]<<'\n';
    return 0;
}

Subtask #1

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Incorrect	1 ms	340 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #2

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Incorrect	1 ms	340 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #3

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	488 ms	29692 KB	Output is correct
2	Correct	480 ms	29636 KB	Output is correct
3	Correct	491 ms	29632 KB	Output is correct
4	Correct	495 ms	29648 KB	Output is correct
5	Incorrect	468 ms	29620 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #4

0 / 17.0

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

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Incorrect	1 ms	340 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #6

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Incorrect	1 ms	340 KB	Output isn't correct
11	Halted	0 ms	0 KB	-