oj.uz

Submission #497540

# Submission time Handle Problem Language Result Execution time Memory
497540 2021-12-23T08:23:04 Z kingline Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 685 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 = upper_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 47 ms 94228 KB Output is correct
2 Correct 47 ms 94200 KB Output is correct
3 Correct 50 ms 94236 KB Output is correct
4 Correct 50 ms 94152 KB Output is correct
5 Correct 43 ms 94220 KB Output is correct
6 Correct 47 ms 94168 KB Output is correct
7 Correct 49 ms 94252 KB Output is correct
8 Correct 49 ms 94240 KB Output is correct
9 Correct 60 ms 94152 KB Output is correct
10 Correct 54 ms 94240 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94228 KB Output is correct
2 Correct 47 ms 94200 KB Output is correct
3 Correct 50 ms 94236 KB Output is correct
4 Correct 50 ms 94152 KB Output is correct
5 Correct 43 ms 94220 KB Output is correct
6 Correct 47 ms 94168 KB Output is correct
7 Correct 49 ms 94252 KB Output is correct
8 Correct 49 ms 94240 KB Output is correct
9 Correct 60 ms 94152 KB Output is correct
10 Correct 54 ms 94240 KB Output is correct
11 Correct 54 ms 94236 KB Output is correct
12 Correct 58 ms 94200 KB Output is correct
13 Correct 56 ms 94276 KB Output is correct
14 Correct 61 ms 94176 KB Output is correct
15 Correct 61 ms 94276 KB Output is correct
16 Correct 76 ms 94292 KB Output is correct
17 Correct 80 ms 94292 KB Output is correct
18 Correct 68 ms 94360 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 448 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 359 ms 136280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94228 KB Output is correct
2 Correct 47 ms 94200 KB Output is correct
3 Correct 50 ms 94236 KB Output is correct
4 Correct 50 ms 94152 KB Output is correct
5 Correct 43 ms 94220 KB Output is correct
6 Correct 47 ms 94168 KB Output is correct
7 Correct 49 ms 94252 KB Output is correct
8 Correct 49 ms 94240 KB Output is correct
9 Correct 60 ms 94152 KB Output is correct
10 Correct 54 ms 94240 KB Output is correct
11 Correct 54 ms 94236 KB Output is correct
12 Correct 58 ms 94200 KB Output is correct
13 Correct 56 ms 94276 KB Output is correct
14 Correct 61 ms 94176 KB Output is correct
15 Correct 61 ms 94276 KB Output is correct
16 Correct 76 ms 94292 KB Output is correct
17 Correct 80 ms 94292 KB Output is correct
18 Correct 68 ms 94360 KB Output is correct
19 Incorrect 685 ms 181576 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94228 KB Output is correct
2 Correct 47 ms 94200 KB Output is correct
3 Correct 50 ms 94236 KB Output is correct
4 Correct 50 ms 94152 KB Output is correct
5 Correct 43 ms 94220 KB Output is correct
6 Correct 47 ms 94168 KB Output is correct
7 Correct 49 ms 94252 KB Output is correct
8 Correct 49 ms 94240 KB Output is correct
9 Correct 60 ms 94152 KB Output is correct
10 Correct 54 ms 94240 KB Output is correct
11 Correct 54 ms 94236 KB Output is correct
12 Correct 58 ms 94200 KB Output is correct
13 Correct 56 ms 94276 KB Output is correct
14 Correct 61 ms 94176 KB Output is correct
15 Correct 61 ms 94276 KB Output is correct
16 Correct 76 ms 94292 KB Output is correct
17 Correct 80 ms 94292 KB Output is correct
18 Correct 68 ms 94360 KB Output is correct
19 Runtime error 448 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -