oj.uz

Submission #349343

# Submission time Handle Problem Language Result Execution time Memory
349343 2021-01-17T12:41:07 Z Sara Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 2031 ms 86972 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll unsigned long long
#define F first
#define S second
#define pb push_back
#define lc (ind << 1)
#define rc (lc | 1)
#define md ((b + e) >> 1)
#define poo pair < int, pair <int, int> >

const ll N = 1e6 + 5;
const ll LOG = 20;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 5;

string s;
int n, a[N], q, L[N], P[N];
int mx[4 * N], maxi[4 * N];
vector <int> all[N];
bool ans[N];

void add(int l, int r, int id, int b = 0, int e = n, int ind = 1){
    if (l <= b && e <= r){
        if (a[id] < mx[ind]){
            maxi[ind] = max(maxi[ind], a[id] + mx[ind]);
        }
        return;
    }
    if (l < md) add(l, r, id, b, md, lc);
    if (md < r) add(l, r, id, md, e, rc);
    maxi[ind] = max(maxi[lc], maxi[rc]); 
    return;
}

void push(int id, int b = 0, int e = n, int ind = 1){
    if (b + 1 == e){
        mx[ind] = a[b];
        return;
    }
    if (id < md) push(id, b, md, lc);
    else push(id, md, e, rc);
    mx[ind] = max(mx[lc], mx[rc]);
    return;
}

int get(int l, int r, int b = 0, int e = n, int ind = 1){
    if (l <= b && e <= r) return maxi[ind];
    int ret = 0;
    if (l < md) ret = max(ret, get(l, r, b, md, lc));
    if (md < r) ret = max(ret, get(l, r, md, e, rc));
    return ret; 
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n; i ++){
        cin >> a[i];
    }
    for (int i = 0; i < q; i ++){
        int R;
        cin >> L[i] >> R >> P[i]; L[i] --;
        all[R].pb(i);
    }
    push(0);
    for (int i = 1; i <= n; i ++){
        if (i != n){
            push(i);
            add(0, i, i);
        }
        for (int id : all[i]){
            ans[id] = (get(L[id], i) <= P[id]);
        }
    }
    for (int i = 0; i < q; i ++){
        cout << ans[i] << '\n';
    }
    return 0;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 23.0

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