oj.uz

Submission #511480

# Submission time Handle Problem Language Result Execution time Memory
511480 2022-01-16T00:10:42 Z Gev2706 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 164608 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; i + (1 << j) < n; j++)
                sp[i][j] = min(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
        }

        while (m--) {
            int l, r, k; cin >> l >> r >> k;
            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 0 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 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 13 ms 204 KB Output is correct
7 Correct 12 ms 332 KB Output is correct
8 Correct 18 ms 204 KB Output is correct
9 Correct 8 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 13 ms 204 KB Output is correct
7 Correct 12 ms 332 KB Output is correct
8 Correct 18 ms 204 KB Output is correct
9 Correct 8 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 214 ms 420 KB Output is correct
12 Correct 732 ms 712 KB Output is correct
13 Correct 842 ms 708 KB Output is correct
14 Correct 1413 ms 672 KB Output is correct
15 Correct 1443 ms 712 KB Output is correct
16 Correct 2285 ms 712 KB Output is correct
17 Correct 1613 ms 588 KB Output is correct
18 Correct 124 ms 332 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3002 ms 164608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 248 ms 17584 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 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 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 13 ms 204 KB Output is correct
7 Correct 12 ms 332 KB Output is correct
8 Correct 18 ms 204 KB Output is correct
9 Correct 8 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 214 ms 420 KB Output is correct
12 Correct 732 ms 712 KB Output is correct
13 Correct 842 ms 708 KB Output is correct
14 Correct 1413 ms 672 KB Output is correct
15 Correct 1443 ms 712 KB Output is correct
16 Correct 2285 ms 712 KB Output is correct
17 Correct 1613 ms 588 KB Output is correct
18 Correct 124 ms 332 KB Output is correct
19 Incorrect 596 ms 36468 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 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 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 13 ms 204 KB Output is correct
7 Correct 12 ms 332 KB Output is correct
8 Correct 18 ms 204 KB Output is correct
9 Correct 8 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 214 ms 420 KB Output is correct
12 Correct 732 ms 712 KB Output is correct
13 Correct 842 ms 708 KB Output is correct
14 Correct 1413 ms 672 KB Output is correct
15 Correct 1443 ms 712 KB Output is correct
16 Correct 2285 ms 712 KB Output is correct
17 Correct 1613 ms 588 KB Output is correct
18 Correct 124 ms 332 KB Output is correct
19 Execution timed out 3002 ms 164608 KB Time limit exceeded
20 Halted 0 ms 0 KB -