oj.uz

Submission #511484

# Submission time Handle Problem Language Result Execution time Memory
511484 2022-01-16T00:19:36 Z Gev2706 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
17 / 100
 3000 ms 179884 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
vector<int> l2(1e6 + 5, 0);

int query(int& l, int& r, vector<vector<int>> &s) {
    int t = r - l + 1;
    t = l2[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()] = i;
                st.pop();
            }
            st.push(i);
        }
        while (!st.empty())
        {
            v[st.top()] = 2e9;
            st.pop();
        }
        vector<vector<int>> sp(n + 5, vector<int>(25, 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--;
            if (query(l, r, sp) <= r) {
                cout << 0 << endl;
            }
            else cout << 1 << endl;
        }
    }
}
int main()
{
    //int tc; cin >> tc;while(tc--)
    l2[1] = 0;

    for (int i = 2; i <= 1e6 + 2; i++)
        l2[i] = l2[i / 2] + 1;
    solve();
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4172 KB Output is correct
2 Correct 3 ms 4172 KB Output is correct
3 Correct 6 ms 4172 KB Output is correct
4 Correct 3 ms 4172 KB Output is correct
5 Correct 3 ms 4172 KB Output is correct
6 Correct 15 ms 4172 KB Output is correct
7 Correct 14 ms 4172 KB Output is correct
8 Correct 21 ms 4172 KB Output is correct
9 Correct 11 ms 4172 KB Output is correct
10 Correct 4 ms 4172 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4172 KB Output is correct
2 Correct 3 ms 4172 KB Output is correct
3 Correct 6 ms 4172 KB Output is correct
4 Correct 3 ms 4172 KB Output is correct
5 Correct 3 ms 4172 KB Output is correct
6 Correct 15 ms 4172 KB Output is correct
7 Correct 14 ms 4172 KB Output is correct
8 Correct 21 ms 4172 KB Output is correct
9 Correct 11 ms 4172 KB Output is correct
10 Correct 4 ms 4172 KB Output is correct
11 Correct 221 ms 4276 KB Output is correct
12 Correct 758 ms 4432 KB Output is correct
13 Correct 859 ms 4560 KB Output is correct
14 Correct 1463 ms 4568 KB Output is correct
15 Correct 1458 ms 4452 KB Output is correct
16 Correct 2352 ms 4476 KB Output is correct
17 Correct 1630 ms 4416 KB Output is correct
18 Correct 130 ms 4172 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2961 ms 147280 KB Output is correct
2 Correct 2973 ms 147112 KB Output is correct
3 Execution timed out 3012 ms 179884 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4172 KB Output is correct
2 Correct 3 ms 4172 KB Output is correct
3 Correct 6 ms 4172 KB Output is correct
4 Correct 3 ms 4172 KB Output is correct
5 Correct 3 ms 4172 KB Output is correct
6 Correct 15 ms 4172 KB Output is correct
7 Correct 14 ms 4172 KB Output is correct
8 Correct 21 ms 4172 KB Output is correct
9 Correct 11 ms 4172 KB Output is correct
10 Correct 4 ms 4172 KB Output is correct
11 Correct 221 ms 4276 KB Output is correct
12 Correct 758 ms 4432 KB Output is correct
13 Correct 859 ms 4560 KB Output is correct
14 Correct 1463 ms 4568 KB Output is correct
15 Correct 1458 ms 4452 KB Output is correct
16 Correct 2352 ms 4476 KB Output is correct
17 Correct 1630 ms 4416 KB Output is correct
18 Correct 130 ms 4172 KB Output is correct
19 Incorrect 562 ms 32708 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4172 KB Output is correct
2 Correct 3 ms 4172 KB Output is correct
3 Correct 6 ms 4172 KB Output is correct
4 Correct 3 ms 4172 KB Output is correct
5 Correct 3 ms 4172 KB Output is correct
6 Correct 15 ms 4172 KB Output is correct
7 Correct 14 ms 4172 KB Output is correct
8 Correct 21 ms 4172 KB Output is correct
9 Correct 11 ms 4172 KB Output is correct
10 Correct 4 ms 4172 KB Output is correct
11 Correct 221 ms 4276 KB Output is correct
12 Correct 758 ms 4432 KB Output is correct
13 Correct 859 ms 4560 KB Output is correct
14 Correct 1463 ms 4568 KB Output is correct
15 Correct 1458 ms 4452 KB Output is correct
16 Correct 2352 ms 4476 KB Output is correct
17 Correct 1630 ms 4416 KB Output is correct
18 Correct 130 ms 4172 KB Output is correct
19 Correct 2961 ms 147280 KB Output is correct
20 Correct 2973 ms 147112 KB Output is correct
21 Execution timed out 3012 ms 179884 KB Time limit exceeded
22 Halted 0 ms 0 KB -