oj.uz

Submission #511476

# Submission time Handle Problem Language Result Execution time Memory
511476 2022-01-16T00:07:18 Z Gev2706 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 2377 ms 262144 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <string>
#include <sstream>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <stack>
#include <cstdio>
#include <climits>
#include <tuple>
#include <ctime>
#include <cstring>
#include <numeric>
#include <functional>
#include <chrono>
#include <cassert>
#include <bitset>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int N = 5e6 + 5;
#define full(a) a.begin(), a.end()
#define eps 1e-9

int query(int l, int r, vector<vector<int>> &s) {
    int t = r - l + 1;
    t = log2(t);
    return min(s[l][t], s[r - (1 << t) + 1][t]);
}

void solve() {
    int n, m; cin >> n >> m;
    vector<int> w(n);
    for (int i = 0; i < n; i++)cin >> w[i];
    if (n <= 5000 && m <= 5000) {
        while (m--) {
            int l, r, k; cin >> l >> r >> k;
            l--, r--;
            int ans = 1;
            set<int> s;
            s.insert(w[r]);
            for (int i = r - 1; i >= l; i--) {
                auto it = s.lower_bound(w[i]);
                if (it != s.begin()) {
                    it--;
                    if (*it + w[i] > k)ans = 0;
                }
                s.insert(w[i]);
            }
            cout << ans << endl;
        }
    }
    else {
        vector<int> v(n);
        stack<int> st;
        for (int i = 0; i < n; i++) {
            if (st.empty()) {
                st.push(i);
                continue;
            }
            while (!st.empty() && w[st.top()] > w[i]) {
                v[st.top()] = w[i];
                st.pop();
            }
            st.push(i);
        }
        while (!st.empty())
        {
            v[st.top()] = 2e9;
            st.pop();
        }
        vector<vector<int>> sp(n + 5, vector<int>(30, 0));
        for (int i = 0; i < n; i++)sp[i][0] = v[i];
        for (int i = 0; i < n; i++) {
            for (int j = 1; j + (1 << i) < n; j++)
                sp[i][j] = min(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
        }

        while (m--) {
            int l, r; cin >> l >> r;
            l--, r--;
            cout << query(l, r, sp) << endl;
        }
    }
}
int main()
{
    //int tc; cin >> tc;while(tc--)
    solve();
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 3 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 204 KB Output is correct
6 Correct 13 ms 300 KB Output is correct
7 Correct 12 ms 332 KB Output is correct
8 Correct 19 ms 332 KB Output is correct
9 Correct 9 ms 204 KB Output is correct
10 Correct 3 ms 204 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 3 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 204 KB Output is correct
6 Correct 13 ms 300 KB Output is correct
7 Correct 12 ms 332 KB Output is correct
8 Correct 19 ms 332 KB Output is correct
9 Correct 9 ms 204 KB Output is correct
10 Correct 3 ms 204 KB Output is correct
11 Correct 211 ms 420 KB Output is correct
12 Correct 740 ms 616 KB Output is correct
13 Correct 845 ms 624 KB Output is correct
14 Correct 1433 ms 800 KB Output is correct
15 Correct 1437 ms 796 KB Output is correct
16 Correct 2377 ms 640 KB Output is correct
17 Correct 1673 ms 588 KB Output is correct
18 Correct 135 ms 376 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 623 ms 262144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 32052 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 3 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 204 KB Output is correct
6 Correct 13 ms 300 KB Output is correct
7 Correct 12 ms 332 KB Output is correct
8 Correct 19 ms 332 KB Output is correct
9 Correct 9 ms 204 KB Output is correct
10 Correct 3 ms 204 KB Output is correct
11 Correct 211 ms 420 KB Output is correct
12 Correct 740 ms 616 KB Output is correct
13 Correct 845 ms 624 KB Output is correct
14 Correct 1433 ms 800 KB Output is correct
15 Correct 1437 ms 796 KB Output is correct
16 Correct 2377 ms 640 KB Output is correct
17 Correct 1673 ms 588 KB Output is correct
18 Correct 135 ms 376 KB Output is correct
19 Runtime error 112 ms 63852 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 3 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 204 KB Output is correct
6 Correct 13 ms 300 KB Output is correct
7 Correct 12 ms 332 KB Output is correct
8 Correct 19 ms 332 KB Output is correct
9 Correct 9 ms 204 KB Output is correct
10 Correct 3 ms 204 KB Output is correct
11 Correct 211 ms 420 KB Output is correct
12 Correct 740 ms 616 KB Output is correct
13 Correct 845 ms 624 KB Output is correct
14 Correct 1433 ms 800 KB Output is correct
15 Correct 1437 ms 796 KB Output is correct
16 Correct 2377 ms 640 KB Output is correct
17 Correct 1673 ms 588 KB Output is correct
18 Correct 135 ms 376 KB Output is correct
19 Runtime error 623 ms 262144 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -