oj.uz

Submission #651225

# Submission time Handle Problem Language Result Execution time Memory
651225 2022-10-18T03:15:45 Z becaido Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
30 / 100
 519 ms 10212 KB 
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a,I=b;x<=I;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e6 + 5;

int n, q;
int a[SIZE], to[SIZE];

void solve2() {
    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        int mx = 0;
        bool f = 1;
        FOR (i, l, r) {
            if (mx > max (a[i], k - a[i])) {
                f = 0;
                break;
            }
            mx = max (mx, a[i]);
        }
        cout << f << '\n';
    }
}

void solve() {
    cin >> n >> q;
    FOR (i, 1, n) cin >> a[i];
    if (n <= 5000) {
        solve2();
        return;
    }
    int cnt = 0;
    FOR (i, 1, n) {
        FOR (j, i, n) {
            if (j == n || a[j + 1] < a[j]) {
                FOR (k, i, j) to[k] = cnt;
                cnt++;
                i = j;
                break;
            }
        }
    }
    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        cout << (to[l] == to[r]) << '\n';
    }
}

int main() {
    Waimai;
    solve();
}
/*
5 2
3 5 1 8 2
1 3 6
2 5 3
*/

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 14 ms 356 KB Output is correct
17 Correct 14 ms 356 KB Output is correct
18 Correct 13 ms 340 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 10060 KB Output is correct
2 Correct 499 ms 10136 KB Output is correct
3 Correct 497 ms 10084 KB Output is correct
4 Correct 477 ms 10212 KB Output is correct
5 Correct 487 ms 10056 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 14 ms 356 KB Output is correct
17 Correct 14 ms 356 KB Output is correct
18 Correct 13 ms 340 KB Output is correct
19 Incorrect 96 ms 2232 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 14 ms 356 KB Output is correct
17 Correct 14 ms 356 KB Output is correct
18 Correct 13 ms 340 KB Output is correct
19 Correct 519 ms 10060 KB Output is correct
20 Correct 499 ms 10136 KB Output is correct
21 Correct 497 ms 10084 KB Output is correct
22 Correct 477 ms 10212 KB Output is correct
23 Correct 487 ms 10056 KB Output is correct
24 Incorrect 39 ms 1216 KB Output isn't correct
25 Halted 0 ms 0 KB -