oj.uz

Submission #497543

# Submission time Handle Problem Language Result Execution time Memory
497543 2021-12-23T08:29:06 Z kingline Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 595 ms 262148 KB 
/*#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")*/
#include <bits/stdc++.h>
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
//#define file(data) freopen(data".in", "r", stdin); freopen(data".out", "w", stdout);
#define pb push_back
//#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(data) data.begin() , data.end()
#define endl '\n'
//freopen("nenokku_easy.in", "r", stdin);
//freopen("nenokku_easy.out", "w", stdout);
#define int long long
#define pii pair < int, int >
#define pll pair < long long, long long >

using namespace std;

typedef long long ll;
const int N = 1e6 + 5;
const int M = 5005;
const int mod = 1e9 + 7;

int n, m, w[N];
pii mt[4 * N];
vector < int > t[4 * N];

pii combine(pii x, pii y) {
    if(x.first >= y.first) return x;
    else return y;
}

void build(int v, int l, int r) {
    if(l == r) {
        mt[v] = {w[l], l};
        t[v].pb(w[l]);
        t[v].pb(mod);
        return;
    }
    int md = (l + r) / 2;
    build(v * 2, l, md);
    build(v * 2 + 1, md + 1, r);
    mt[v] = combine(mt[v * 2], mt[v * 2 + 1]);
    merge(all(t[v * 2]), all(t[v * 2 + 1]), back_inserter(t[v]));
}

pii get(int v, int l, int r, int tl, int tr) {
    if(tl <= l && r <= tr) {
        return mt[v];
    }
    if(r < tl || tr < l) return {-1, -1};
    int md = (l + r) / 2;
    return combine(get(v * 2, l, md, tl ,tr), get(v * 2 + 1, md + 1, r, tl, tr));
}

int get2(int v, int l, int r, int tl, int tr, int x) {
    if(l > r) return -1;
    if(tl <= l && r <= tr) {
        int pos = lower_bound(all(t[v]), x) - t[v].begin();
        if(pos == 0) return -1;
        return t[v][pos - 1];
    }
    if(r < tl || tr < l) return -1;
    int md = (l + r) / 2;
    return max(get2(v * 2, l, md, tl, tr, x),
               get2(v * 2 + 1, md + 1, r, tl, tr, x));
}

main() {
    //file("pieaters");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    if(n <= 5000 && m <= 5000) {
        while(m--) {
            int l, r, k;
            cin >> l >> r >> k;
            bool ok = 1;
            int mx = 0;
            for(int j = l; j <= r; j++) {
                if(mx + w[j] > k && mx > w[j]) {
                    ok = 0;
                    break;
                }
                mx = max(mx, w[j]);
            }
            cout << ok << endl;
        }
    } else {
        build(1, 1, n);
        while(m--) {
            int l, r, k;
            cin >> l >> r >> k;
            bool ok = 1;
            pii gt = get(1, 1, n, l, r);
            int gt2 = get2(1, 1, n, gt.second + 1, r, gt.first);
            if(gt.first + gt2 > k) ok = 0;
            cout << ok << endl;
        }
    }
}

Compilation message

sortbooks.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main() {
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94188 KB Output is correct
2 Correct 47 ms 94212 KB Output is correct
3 Correct 47 ms 94200 KB Output is correct
4 Correct 48 ms 94204 KB Output is correct
5 Correct 54 ms 94148 KB Output is correct
6 Correct 46 ms 94248 KB Output is correct
7 Correct 59 ms 94248 KB Output is correct
8 Correct 46 ms 94156 KB Output is correct
9 Correct 46 ms 94164 KB Output is correct
10 Correct 51 ms 94196 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94188 KB Output is correct
2 Correct 47 ms 94212 KB Output is correct
3 Correct 47 ms 94200 KB Output is correct
4 Correct 48 ms 94204 KB Output is correct
5 Correct 54 ms 94148 KB Output is correct
6 Correct 46 ms 94248 KB Output is correct
7 Correct 59 ms 94248 KB Output is correct
8 Correct 46 ms 94156 KB Output is correct
9 Correct 46 ms 94164 KB Output is correct
10 Correct 51 ms 94196 KB Output is correct
11 Correct 51 ms 94228 KB Output is correct
12 Correct 53 ms 94192 KB Output is correct
13 Correct 52 ms 94260 KB Output is correct
14 Correct 51 ms 94292 KB Output is correct
15 Correct 62 ms 94324 KB Output is correct
16 Correct 61 ms 94304 KB Output is correct
17 Correct 59 ms 94280 KB Output is correct
18 Correct 68 ms 94256 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 351 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94188 KB Output is correct
2 Correct 47 ms 94212 KB Output is correct
3 Correct 47 ms 94200 KB Output is correct
4 Correct 48 ms 94204 KB Output is correct
5 Correct 54 ms 94148 KB Output is correct
6 Correct 46 ms 94248 KB Output is correct
7 Correct 59 ms 94248 KB Output is correct
8 Correct 46 ms 94156 KB Output is correct
9 Correct 46 ms 94164 KB Output is correct
10 Correct 51 ms 94196 KB Output is correct
11 Correct 51 ms 94228 KB Output is correct
12 Correct 53 ms 94192 KB Output is correct
13 Correct 52 ms 94260 KB Output is correct
14 Correct 51 ms 94292 KB Output is correct
15 Correct 62 ms 94324 KB Output is correct
16 Correct 61 ms 94304 KB Output is correct
17 Correct 59 ms 94280 KB Output is correct
18 Correct 68 ms 94256 KB Output is correct
19 Incorrect 595 ms 181584 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94188 KB Output is correct
2 Correct 47 ms 94212 KB Output is correct
3 Correct 47 ms 94200 KB Output is correct
4 Correct 48 ms 94204 KB Output is correct
5 Correct 54 ms 94148 KB Output is correct
6 Correct 46 ms 94248 KB Output is correct
7 Correct 59 ms 94248 KB Output is correct
8 Correct 46 ms 94156 KB Output is correct
9 Correct 46 ms 94164 KB Output is correct
10 Correct 51 ms 94196 KB Output is correct
11 Correct 51 ms 94228 KB Output is correct
12 Correct 53 ms 94192 KB Output is correct
13 Correct 52 ms 94260 KB Output is correct
14 Correct 51 ms 94292 KB Output is correct
15 Correct 62 ms 94324 KB Output is correct
16 Correct 61 ms 94304 KB Output is correct
17 Correct 59 ms 94280 KB Output is correct
18 Correct 68 ms 94256 KB Output is correct
19 Runtime error 351 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -