oj.uz

Submission #919219

# Submission time Handle Problem Language Result Execution time Memory
919219 2024-01-31T13:09:08 Z Whisper Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 142 ms 25296 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using T = tuple<ll, ll, ll>;

#define int long long
#define Base 41
#define sz(a) (int)a.size()
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)
#define all(x) x.begin() , x.end()
#define pii pair<int , int>
#define fi first
#define se second
#define Lg(x) 31 - __builtin_clz(x)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int MAX = 2e5 + 5;
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
int N, Q;
int a[MAX];
//l(i) là thằng gần nhất > a(i) về bên trái mà a(i) + a(l(i)) > K

int leftMost[MAX];

vector<array<int, 3>> que[MAX];
int f[MAX];
void modify(int p, int val){
    for ( ; p > 0; p -= p & (-p)) maximize(f[p], val);
}
int query(int p){
    int res = 0;
    for ( ; p <= N; p += p & (-p)) maximize(res, f[p]);
    return res;
}
int ans[MAX];
void Whisper(){
    cin >> N >> Q;
    for (int i = 1; i <= N; ++i) cin >> a[i];
    stack<int> st;
    for (int i = 1; i <= N; ++i){
        while (st.size() && a[st.top()] <= a[i]) st.pop();
        if (st.size()) leftMost[i] = st.top();
        st.push(i);
    }
    for (int i = 1; i <= Q; ++i){
        int l, r, k; cin >> l >> r >> k;
        que[r].push_back({l, k, i});
    }
    for (int r = 1; r <= N; ++r){
        if (leftMost[r] > 0) modify(leftMost[r], a[leftMost[r]] + a[r]);
        for (auto&[l, k, id] : que[r]){
            ans[id] = (query(l) <= k);
        }
    }
    FOR(i, 1, Q) cout << ans[i] << "\n";
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 3 ms 8536 KB Output is correct
4 Correct 3 ms 8536 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8536 KB Output is correct
8 Correct 3 ms 8536 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8536 KB Output is correct
11 Correct 4 ms 8792 KB Output is correct
12 Correct 3 ms 8792 KB Output is correct
13 Correct 4 ms 8792 KB Output is correct
14 Correct 6 ms 9044 KB Output is correct
15 Correct 5 ms 9048 KB Output is correct
16 Correct 4 ms 8792 KB Output is correct
17 Correct 5 ms 8792 KB Output is correct
18 Correct 4 ms 8792 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 20320 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 53 ms 15572 KB Output is correct
2 Correct 44 ms 15700 KB Output is correct
3 Correct 41 ms 14840 KB Output is correct
4 Correct 49 ms 14712 KB Output is correct
5 Correct 40 ms 14672 KB Output is correct
6 Correct 33 ms 14672 KB Output is correct
7 Correct 37 ms 14672 KB Output is correct
8 Correct 39 ms 14288 KB Output is correct
9 Correct 25 ms 13828 KB Output is correct
10 Correct 43 ms 14084 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 3 ms 8536 KB Output is correct
4 Correct 3 ms 8536 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8536 KB Output is correct
8 Correct 3 ms 8536 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8536 KB Output is correct
11 Correct 4 ms 8792 KB Output is correct
12 Correct 3 ms 8792 KB Output is correct
13 Correct 4 ms 8792 KB Output is correct
14 Correct 6 ms 9044 KB Output is correct
15 Correct 5 ms 9048 KB Output is correct
16 Correct 4 ms 8792 KB Output is correct
17 Correct 5 ms 8792 KB Output is correct
18 Correct 4 ms 8792 KB Output is correct
19 Correct 135 ms 24692 KB Output is correct
20 Correct 131 ms 24912 KB Output is correct
21 Correct 100 ms 25168 KB Output is correct
22 Correct 105 ms 25152 KB Output is correct
23 Correct 95 ms 25296 KB Output is correct
24 Correct 92 ms 24544 KB Output is correct
25 Correct 89 ms 24652 KB Output is correct
26 Correct 109 ms 24644 KB Output is correct
27 Correct 107 ms 24456 KB Output is correct
28 Correct 127 ms 24612 KB Output is correct
29 Correct 119 ms 24144 KB Output is correct
30 Correct 126 ms 24144 KB Output is correct
31 Correct 130 ms 24144 KB Output is correct
32 Correct 130 ms 24140 KB Output is correct
33 Correct 142 ms 24172 KB Output is correct
34 Correct 86 ms 23808 KB Output is correct
35 Correct 90 ms 23896 KB Output is correct
36 Correct 76 ms 23764 KB Output is correct
37 Correct 82 ms 23720 KB Output is correct
38 Correct 90 ms 23888 KB Output is correct
39 Correct 108 ms 22316 KB Output is correct
40 Correct 117 ms 20628 KB Output is correct
41 Correct 117 ms 22824 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 3 ms 8536 KB Output is correct
4 Correct 3 ms 8536 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8536 KB Output is correct
8 Correct 3 ms 8536 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8536 KB Output is correct
11 Correct 4 ms 8792 KB Output is correct
12 Correct 3 ms 8792 KB Output is correct
13 Correct 4 ms 8792 KB Output is correct
14 Correct 6 ms 9044 KB Output is correct
15 Correct 5 ms 9048 KB Output is correct
16 Correct 4 ms 8792 KB Output is correct
17 Correct 5 ms 8792 KB Output is correct
18 Correct 4 ms 8792 KB Output is correct
19 Runtime error 25 ms 20320 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -