oj.uz

Submission #859790

# Submission time Handle Problem Language Result Execution time Memory
859790 2023-10-10T15:58:20 Z Alfraganus Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
30 / 100
 3000 ms 27040 KB 
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ll long long
#define all(a) a.begin(), a.end()
#define fastio ios::sync_with_stdio(0), cin.tie(0);
#define fs first
#define ss second

#define print(a)          \
    for (auto x : a)      \
        cout << x << ' '; \
    cout << endl;

#define printmp(a)   \
    for (auto x : a) \
        cout << x.fs << ' ' << x.ss << endl;

void solve()
{
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    int mn = 1e9;
    for (int i = 0; i < n; i++)
        cin >> a[i], mn = min(mn, a[i]);
    vector<int> dp(n);
    for(int i = 0; i < n - 1; i ++)
        dp[i + 1] = a[i + 1] < a[i];
    for(int i = 1; i < n; i ++)
        dp[i] += dp[i - 1];
    while (q--)
    {
        int l, r, k;
        cin >> l >> r >> k;
        bool flag = 1;
        l--;
        r--;
        if(mn > k){
            cout << (dp[l] == dp[r]) << endl;
            continue;
        }
        int mx = 0;
        for (int i = l; i <= r; i++)
        {
            if(mx > a[i] and mx + a[i] > k){
                flag = 0;
                break;
            }
            mx = max(mx, a[i]);
        }
        if (flag)
            cout << 1 << endl;
        else
            cout << 0 << endl;
    }
}

signed main()
{
    fastio
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
        cout << endl;
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 4 ms 464 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 13 ms 604 KB Output is correct
17 Correct 11 ms 600 KB Output is correct
18 Correct 12 ms 348 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 26612 KB Output is correct
2 Correct 426 ms 27040 KB Output is correct
3 Correct 463 ms 26944 KB Output is correct
4 Correct 472 ms 26992 KB Output is correct
5 Correct 525 ms 26688 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 2644 KB Output is correct
2 Correct 1190 ms 2464 KB Output is correct
3 Execution timed out 3044 ms 2384 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 4 ms 464 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 13 ms 604 KB Output is correct
17 Correct 11 ms 600 KB Output is correct
18 Correct 12 ms 348 KB Output is correct
19 Correct 1466 ms 5936 KB Output is correct
20 Correct 1421 ms 5844 KB Output is correct
21 Execution timed out 3010 ms 4772 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 4 ms 464 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 13 ms 604 KB Output is correct
17 Correct 11 ms 600 KB Output is correct
18 Correct 12 ms 348 KB Output is correct
19 Correct 450 ms 26612 KB Output is correct
20 Correct 426 ms 27040 KB Output is correct
21 Correct 463 ms 26944 KB Output is correct
22 Correct 472 ms 26992 KB Output is correct
23 Correct 525 ms 26688 KB Output is correct
24 Correct 415 ms 2644 KB Output is correct
25 Correct 1190 ms 2464 KB Output is correct
26 Execution timed out 3044 ms 2384 KB Time limit exceeded
27 Halted 0 ms 0 KB -