oj.uz

Submission #511487

# Submission time Handle Problem Language Result Execution time Memory
511487 2022-01-16T00:24:30 Z Gev2706 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 127544 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) {
    return min(s[l][l2[r - l + 1]], s[r - (1 << l2[r - l + 1]) + 1][l2[r - l + 1]]);
}

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]) {
                w[st.top()] = i;
                st.pop();
            }
            st.push(i);
        }
        while (!st.empty())
        {
            w[st.top()] = 2e9;
            st.pop();
        }
        vector<vector<int>> sp(n, vector<int>(21, 0));
        for (int i = 0; i < n; i++)sp[i][0] = w[i];
        for (int j = 1; j <= 20; j++) {
            for (int i = 0; i + (1 << j) < n; i++) {
                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 3 ms 4172 KB Output is correct
2 Correct 2 ms 4172 KB Output is correct
3 Correct 5 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 16 ms 4172 KB Output is correct
7 Correct 16 ms 4172 KB Output is correct
8 Correct 20 ms 4172 KB Output is correct
9 Correct 10 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 3 ms 4172 KB Output is correct
2 Correct 2 ms 4172 KB Output is correct
3 Correct 5 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 16 ms 4172 KB Output is correct
7 Correct 16 ms 4172 KB Output is correct
8 Correct 20 ms 4172 KB Output is correct
9 Correct 10 ms 4172 KB Output is correct
10 Correct 4 ms 4172 KB Output is correct
11 Correct 230 ms 4288 KB Output is correct
12 Correct 765 ms 4440 KB Output is correct
13 Correct 874 ms 4452 KB Output is correct
14 Correct 1424 ms 4576 KB Output is correct
15 Correct 1452 ms 4460 KB Output is correct
16 Correct 2413 ms 4576 KB Output is correct
17 Correct 1720 ms 4408 KB Output is correct
18 Correct 120 ms 4228 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2967 ms 127544 KB Output is correct
2 Correct 2990 ms 127532 KB Output is correct
3 Execution timed out 3032 ms 127536 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 2 ms 4172 KB Output is correct
3 Correct 5 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 16 ms 4172 KB Output is correct
7 Correct 16 ms 4172 KB Output is correct
8 Correct 20 ms 4172 KB Output is correct
9 Correct 10 ms 4172 KB Output is correct
10 Correct 4 ms 4172 KB Output is correct
11 Correct 230 ms 4288 KB Output is correct
12 Correct 765 ms 4440 KB Output is correct
13 Correct 874 ms 4452 KB Output is correct
14 Correct 1424 ms 4576 KB Output is correct
15 Correct 1452 ms 4460 KB Output is correct
16 Correct 2413 ms 4576 KB Output is correct
17 Correct 1720 ms 4408 KB Output is correct
18 Correct 120 ms 4228 KB Output is correct
19 Incorrect 597 ms 28944 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 2 ms 4172 KB Output is correct
3 Correct 5 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 16 ms 4172 KB Output is correct
7 Correct 16 ms 4172 KB Output is correct
8 Correct 20 ms 4172 KB Output is correct
9 Correct 10 ms 4172 KB Output is correct
10 Correct 4 ms 4172 KB Output is correct
11 Correct 230 ms 4288 KB Output is correct
12 Correct 765 ms 4440 KB Output is correct
13 Correct 874 ms 4452 KB Output is correct
14 Correct 1424 ms 4576 KB Output is correct
15 Correct 1452 ms 4460 KB Output is correct
16 Correct 2413 ms 4576 KB Output is correct
17 Correct 1720 ms 4408 KB Output is correct
18 Correct 120 ms 4228 KB Output is correct
19 Correct 2967 ms 127544 KB Output is correct
20 Correct 2990 ms 127532 KB Output is correct
21 Execution timed out 3032 ms 127536 KB Time limit exceeded
22 Halted 0 ms 0 KB -