oj.uz

Submission #868503

# Submission time Handle Problem Language Result Execution time Memory
868503 2023-10-31T15:04:24 Z hqminhuwu Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 101 ms 38232 KB 
#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 5e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;

int bit[N],n;
void update (int u, int val){
    for (; u > 0; u -= u & -u)
        bit[u] = max (bit[u],val);
}

int get (int u){
    int res = 0;
    for (; u <= n; u += u & -u)
        res = max (res,bit[u]);
    return res;
}

stack <int> s;
int q,i,a[N],u,v,h[N],ans[N];
vector <pii> g[N];
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    forr (i,1,n)
        cin >> a[i];
    forr (i,1,q){
        cin >> u >> v;
        cin >> h[i];
        g[v].pb({i,u});
    }
    
    forr (i,1,n){
        while (!s.empty() && a[i] >= a[s.top()])
            s.pop();
        if (!s.empty())
            update(s.top(),a[i] + a[s.top()]);
        s.push(i);
        for (pii w : g[i])
            ans[w.st] = get(w.nd);
    }
    forr (i,1,q)
        cout << (ans[i] <= h[i]) << "\n";
    return 0;
}
/*



*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 3 ms 19036 KB Output is correct
4 Correct 3 ms 19032 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 3 ms 19112 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 3 ms 19036 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 3 ms 19036 KB Output is correct
4 Correct 3 ms 19032 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 3 ms 19112 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 3 ms 19036 KB Output is correct
11 Correct 6 ms 19292 KB Output is correct
12 Correct 5 ms 19260 KB Output is correct
13 Correct 6 ms 19036 KB Output is correct
14 Correct 6 ms 19292 KB Output is correct
15 Correct 7 ms 19292 KB Output is correct
16 Correct 5 ms 19292 KB Output is correct
17 Correct 5 ms 19292 KB Output is correct
18 Correct 5 ms 19288 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 38232 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 21020 KB Output is correct
2 Correct 40 ms 22588 KB Output is correct
3 Correct 40 ms 22868 KB Output is correct
4 Correct 39 ms 22864 KB Output is correct
5 Correct 39 ms 23056 KB Output is correct
6 Correct 32 ms 22100 KB Output is correct
7 Correct 37 ms 22088 KB Output is correct
8 Correct 38 ms 22620 KB Output is correct
9 Correct 26 ms 21452 KB Output is correct
10 Correct 38 ms 22488 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 3 ms 19036 KB Output is correct
4 Correct 3 ms 19032 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 3 ms 19112 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 3 ms 19036 KB Output is correct
11 Correct 6 ms 19292 KB Output is correct
12 Correct 5 ms 19260 KB Output is correct
13 Correct 6 ms 19036 KB Output is correct
14 Correct 6 ms 19292 KB Output is correct
15 Correct 7 ms 19292 KB Output is correct
16 Correct 5 ms 19292 KB Output is correct
17 Correct 5 ms 19292 KB Output is correct
18 Correct 5 ms 19288 KB Output is correct
19 Correct 99 ms 29196 KB Output is correct
20 Correct 97 ms 29264 KB Output is correct
21 Correct 101 ms 28172 KB Output is correct
22 Correct 97 ms 28036 KB Output is correct
23 Correct 85 ms 28240 KB Output is correct
24 Correct 77 ms 27732 KB Output is correct
25 Correct 76 ms 27828 KB Output is correct
26 Correct 82 ms 28404 KB Output is correct
27 Correct 82 ms 28572 KB Output is correct
28 Correct 85 ms 28752 KB Output is correct
29 Correct 93 ms 29336 KB Output is correct
30 Correct 99 ms 29356 KB Output is correct
31 Correct 100 ms 29308 KB Output is correct
32 Correct 90 ms 29084 KB Output is correct
33 Correct 94 ms 29292 KB Output is correct
34 Correct 73 ms 27472 KB Output is correct
35 Correct 86 ms 27560 KB Output is correct
36 Correct 73 ms 27216 KB Output is correct
37 Correct 71 ms 27220 KB Output is correct
38 Correct 88 ms 27656 KB Output is correct
39 Correct 84 ms 27900 KB Output is correct
40 Correct 72 ms 26824 KB Output is correct
41 Correct 84 ms 27592 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 3 ms 19036 KB Output is correct
4 Correct 3 ms 19032 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 3 ms 19112 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 3 ms 19036 KB Output is correct
11 Correct 6 ms 19292 KB Output is correct
12 Correct 5 ms 19260 KB Output is correct
13 Correct 6 ms 19036 KB Output is correct
14 Correct 6 ms 19292 KB Output is correct
15 Correct 7 ms 19292 KB Output is correct
16 Correct 5 ms 19292 KB Output is correct
17 Correct 5 ms 19292 KB Output is correct
18 Correct 5 ms 19288 KB Output is correct
19 Runtime error 52 ms 38232 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -