oj.uz

Submission #944033

# Submission time Handle Problem Language Result Execution time Memory
944033 2024-03-12T07:22:52 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
47 / 100
 1632 ms 93896 KB 
#include<bits/stdc++.h>
#define X s.top()
#define K 1<<20
using namespace std;
vector<tuple<int,int,int>>q[1<<20];
int n,a[1<<20],t[1<<20],m,r[1<<20];
void upd(int x,int v){
    for(;x;x-=x&-x)
        t[x]=max(t[x],v);
}
int qu(int x){
    int v=0;
    for(;x<=n;x+=x&-x)
        v=max(t[x],v);
    return v;
}
stack<int>s;
int main(){
    a[0]=1e9,s.push(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=0,a,b,c;i<m;i++)
        cin>>a>>b>>c,q[b].push_back({a,c,i});
    for(int i=1;i<=n;i++){
        while(a[X]<=a[i])
            s.pop();
        if(X) upd(X,a[X]+a[i]);
        s.push(i);
        for(auto[a,b,c]:q[i])
            r[c]=qu(a)<=b;
    }
    for(int i=0;i<m;i++)
        cout<<r[i]<<'\n';
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30808 KB Output is correct
2 Correct 7 ms 30812 KB Output is correct
3 Correct 7 ms 30900 KB Output is correct
4 Correct 7 ms 30812 KB Output is correct
5 Correct 7 ms 31044 KB Output is correct
6 Correct 8 ms 31068 KB Output is correct
7 Correct 9 ms 30808 KB Output is correct
8 Correct 7 ms 31068 KB Output is correct
9 Correct 7 ms 31068 KB Output is correct
10 Correct 7 ms 30812 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30808 KB Output is correct
2 Correct 7 ms 30812 KB Output is correct
3 Correct 7 ms 30900 KB Output is correct
4 Correct 7 ms 30812 KB Output is correct
5 Correct 7 ms 31044 KB Output is correct
6 Correct 8 ms 31068 KB Output is correct
7 Correct 9 ms 30808 KB Output is correct
8 Correct 7 ms 31068 KB Output is correct
9 Correct 7 ms 31068 KB Output is correct
10 Correct 7 ms 30812 KB Output is correct
11 Correct 11 ms 31068 KB Output is correct
12 Correct 11 ms 31068 KB Output is correct
13 Correct 12 ms 31320 KB Output is correct
14 Correct 15 ms 31148 KB Output is correct
15 Correct 13 ms 31320 KB Output is correct
16 Correct 13 ms 31048 KB Output is correct
17 Correct 12 ms 31272 KB Output is correct
18 Correct 11 ms 31320 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1585 ms 92684 KB Output is correct
2 Correct 1632 ms 93896 KB Output is correct
3 Correct 1568 ms 93628 KB Output is correct
4 Correct 1587 ms 93780 KB Output is correct
5 Correct 1566 ms 91696 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 39708 KB Output is correct
2 Correct 99 ms 39464 KB Output is correct
3 Correct 102 ms 39508 KB Output is correct
4 Correct 113 ms 39436 KB Output is correct
5 Correct 130 ms 39436 KB Output is correct
6 Correct 93 ms 38980 KB Output is correct
7 Correct 93 ms 38824 KB Output is correct
8 Correct 94 ms 38920 KB Output is correct
9 Correct 70 ms 36000 KB Output is correct
10 Correct 93 ms 38924 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30808 KB Output is correct
2 Correct 7 ms 30812 KB Output is correct
3 Correct 7 ms 30900 KB Output is correct
4 Correct 7 ms 30812 KB Output is correct
5 Correct 7 ms 31044 KB Output is correct
6 Correct 8 ms 31068 KB Output is correct
7 Correct 9 ms 30808 KB Output is correct
8 Correct 7 ms 31068 KB Output is correct
9 Correct 7 ms 31068 KB Output is correct
10 Correct 7 ms 30812 KB Output is correct
11 Correct 11 ms 31068 KB Output is correct
12 Correct 11 ms 31068 KB Output is correct
13 Correct 12 ms 31320 KB Output is correct
14 Correct 15 ms 31148 KB Output is correct
15 Correct 13 ms 31320 KB Output is correct
16 Correct 13 ms 31048 KB Output is correct
17 Correct 12 ms 31272 KB Output is correct
18 Correct 11 ms 31320 KB Output is correct
19 Correct 313 ms 47104 KB Output is correct
20 Correct 278 ms 46996 KB Output is correct
21 Correct 262 ms 46276 KB Output is correct
22 Correct 263 ms 46416 KB Output is correct
23 Correct 266 ms 46268 KB Output is correct
24 Runtime error 269 ms 84892 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30808 KB Output is correct
2 Correct 7 ms 30812 KB Output is correct
3 Correct 7 ms 30900 KB Output is correct
4 Correct 7 ms 30812 KB Output is correct
5 Correct 7 ms 31044 KB Output is correct
6 Correct 8 ms 31068 KB Output is correct
7 Correct 9 ms 30808 KB Output is correct
8 Correct 7 ms 31068 KB Output is correct
9 Correct 7 ms 31068 KB Output is correct
10 Correct 7 ms 30812 KB Output is correct
11 Correct 11 ms 31068 KB Output is correct
12 Correct 11 ms 31068 KB Output is correct
13 Correct 12 ms 31320 KB Output is correct
14 Correct 15 ms 31148 KB Output is correct
15 Correct 13 ms 31320 KB Output is correct
16 Correct 13 ms 31048 KB Output is correct
17 Correct 12 ms 31272 KB Output is correct
18 Correct 11 ms 31320 KB Output is correct
19 Correct 1585 ms 92684 KB Output is correct
20 Correct 1632 ms 93896 KB Output is correct
21 Correct 1568 ms 93628 KB Output is correct
22 Correct 1587 ms 93780 KB Output is correct
23 Correct 1566 ms 91696 KB Output is correct
24 Correct 106 ms 39708 KB Output is correct
25 Correct 99 ms 39464 KB Output is correct
26 Correct 102 ms 39508 KB Output is correct
27 Correct 113 ms 39436 KB Output is correct
28 Correct 130 ms 39436 KB Output is correct
29 Correct 93 ms 38980 KB Output is correct
30 Correct 93 ms 38824 KB Output is correct
31 Correct 94 ms 38920 KB Output is correct
32 Correct 70 ms 36000 KB Output is correct
33 Correct 93 ms 38924 KB Output is correct
34 Correct 313 ms 47104 KB Output is correct
35 Correct 278 ms 46996 KB Output is correct
36 Correct 262 ms 46276 KB Output is correct
37 Correct 263 ms 46416 KB Output is correct
38 Correct 266 ms 46268 KB Output is correct
39 Runtime error 269 ms 84892 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -