oj.uz

Submission #590616

# Submission time Handle Problem Language Result Execution time Memory
590616 2022-07-06T07:33:59 Z Do_you_copy Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 167 ms 18560 KB 
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000009;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 2e5 + 1;

int n, qq;
int a[maxN];

struct TQuery{
    int l, k, idx;
};
vector <TQuery> q[maxN];

int bit[maxN];
int ans[maxN];

void update(int x, int val){
    for (; x; x -= x & -x){
        bit[x] = max(bit[x], val);
    }
}

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

void Init(){
    cin >> n >> qq;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= qq; ++i){
        int l, r, k;
        cin >> l >> r >> k;
        q[r].pb({l, k, i});
    }
    vector <int> S;
    for (int i = 1; i <= n; ++i){
        while (!S.empty() && a[S.back()] <= a[i]){
            S.pop_back();
        }
        if (!S.empty()){
            update(S.back(), a[i] + a[S.back()]);
        }
        S.pb(i);
        for (auto &j: q[i]){
            //from j -> i
            if (get(j.l, i) <= j.k) ans[j.idx] = 1;
            else ans[j.idx] = 0;
        }
    }
    for (int i = 1; i <= qq; ++i) cout << ans[i] << "\n";
}


int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        //freopen(taskname".out", "w", stdout);
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5060 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5040 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 4 ms 5036 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5060 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5040 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 4 ms 5036 KB Output is correct
11 Correct 5 ms 5204 KB Output is correct
12 Correct 6 ms 5140 KB Output is correct
13 Correct 5 ms 5204 KB Output is correct
14 Correct 7 ms 5268 KB Output is correct
15 Correct 6 ms 5300 KB Output is correct
16 Correct 5 ms 5204 KB Output is correct
17 Correct 4 ms 5176 KB Output is correct
18 Correct 4 ms 5204 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 13644 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 59 ms 10508 KB Output is correct
2 Correct 56 ms 10116 KB Output is correct
3 Correct 67 ms 10084 KB Output is correct
4 Correct 53 ms 10060 KB Output is correct
5 Correct 51 ms 10048 KB Output is correct
6 Correct 42 ms 9516 KB Output is correct
7 Correct 50 ms 9456 KB Output is correct
8 Correct 58 ms 9664 KB Output is correct
9 Correct 45 ms 8412 KB Output is correct
10 Correct 50 ms 9560 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5060 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5040 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 4 ms 5036 KB Output is correct
11 Correct 5 ms 5204 KB Output is correct
12 Correct 6 ms 5140 KB Output is correct
13 Correct 5 ms 5204 KB Output is correct
14 Correct 7 ms 5268 KB Output is correct
15 Correct 6 ms 5300 KB Output is correct
16 Correct 5 ms 5204 KB Output is correct
17 Correct 4 ms 5176 KB Output is correct
18 Correct 4 ms 5204 KB Output is correct
19 Correct 137 ms 18552 KB Output is correct
20 Correct 136 ms 18560 KB Output is correct
21 Correct 123 ms 17920 KB Output is correct
22 Correct 121 ms 17804 KB Output is correct
23 Correct 113 ms 17848 KB Output is correct
24 Correct 129 ms 16908 KB Output is correct
25 Correct 125 ms 17180 KB Output is correct
26 Correct 118 ms 17352 KB Output is correct
27 Correct 121 ms 17312 KB Output is correct
28 Correct 136 ms 17504 KB Output is correct
29 Correct 127 ms 17804 KB Output is correct
30 Correct 118 ms 17808 KB Output is correct
31 Correct 126 ms 17868 KB Output is correct
32 Correct 167 ms 17816 KB Output is correct
33 Correct 145 ms 17684 KB Output is correct
34 Correct 100 ms 16588 KB Output is correct
35 Correct 125 ms 16556 KB Output is correct
36 Correct 108 ms 16256 KB Output is correct
37 Correct 96 ms 16276 KB Output is correct
38 Correct 103 ms 16464 KB Output is correct
39 Correct 135 ms 16228 KB Output is correct
40 Correct 98 ms 14840 KB Output is correct
41 Correct 116 ms 15520 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5060 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5040 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 4 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 4 ms 5036 KB Output is correct
11 Correct 5 ms 5204 KB Output is correct
12 Correct 6 ms 5140 KB Output is correct
13 Correct 5 ms 5204 KB Output is correct
14 Correct 7 ms 5268 KB Output is correct
15 Correct 6 ms 5300 KB Output is correct
16 Correct 5 ms 5204 KB Output is correct
17 Correct 4 ms 5176 KB Output is correct
18 Correct 4 ms 5204 KB Output is correct
19 Runtime error 27 ms 13644 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -