oj.uz

Submission #511513

# Submission time Handle Problem Language Result Execution time Memory
511513 2022-01-16T00:56:14 Z Gev2706 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
30 / 100
 2319 ms 131568 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;

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; scanf("%d%d", &n, &m);
    vector<int> w(n);
    for (int i = 0; i < n; i++)scanf("%d", &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 + 2, vector<int>(22, 0));
        for (int i = 0; i < n; i++)sp[i][0] = v[i];
        for (int j = 1; j <= 21; j++) {
            for (int i = 0; i + (1 << j) < n + 2; i++) {
                sp[i][j] = min(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
            }
        }
        l2.resize(n + 2);
        l2[1] = 0;

        for (int i = 2; i <= n + 1; i++)
            l2[i] = l2[i / 2] + 1;

        while (m--) {
            int l, r, k; scanf("%d%d%d", &l, &r, &k);
            l--, r--;
            if (query(l, r, sp) <= r) {
                printf("0\n");
            }
            else printf("1\n");
        }
    }
}
int main()
{
    //int tc; cin >> tc;while(tc--)

    solve();
    return 0;
}

Compilation message

sortbooks.cpp: In function 'void solve()':
sortbooks.cpp:39:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     int n, m; scanf("%d%d", &n, &m);
      |               ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:41:37: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     for (int i = 0; i < n; i++)scanf("%d", &w[i]);
      |                                ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:93:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |             int l, r, k; scanf("%d%d%d", &l, &r, &k);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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 1 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 13 ms 204 KB Output is correct
8 Correct 19 ms 204 KB Output is correct
9 Correct 10 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 1 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 13 ms 204 KB Output is correct
8 Correct 19 ms 204 KB Output is correct
9 Correct 10 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 212 ms 332 KB Output is correct
12 Correct 725 ms 628 KB Output is correct
13 Correct 830 ms 512 KB Output is correct
14 Correct 1397 ms 516 KB Output is correct
15 Correct 1441 ms 532 KB Output is correct
16 Correct 2319 ms 656 KB Output is correct
17 Correct 1588 ms 608 KB Output is correct
18 Correct 129 ms 204 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 961 ms 131568 KB Output is correct
2 Correct 982 ms 131396 KB Output is correct
3 Correct 999 ms 131556 KB Output is correct
4 Correct 952 ms 131428 KB Output is correct
5 Correct 942 ms 131436 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 13392 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 1 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 13 ms 204 KB Output is correct
8 Correct 19 ms 204 KB Output is correct
9 Correct 10 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 212 ms 332 KB Output is correct
12 Correct 725 ms 628 KB Output is correct
13 Correct 830 ms 512 KB Output is correct
14 Correct 1397 ms 516 KB Output is correct
15 Correct 1441 ms 532 KB Output is correct
16 Correct 2319 ms 656 KB Output is correct
17 Correct 1588 ms 608 KB Output is correct
18 Correct 129 ms 204 KB Output is correct
19 Incorrect 170 ms 26492 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 1 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 13 ms 204 KB Output is correct
8 Correct 19 ms 204 KB Output is correct
9 Correct 10 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 212 ms 332 KB Output is correct
12 Correct 725 ms 628 KB Output is correct
13 Correct 830 ms 512 KB Output is correct
14 Correct 1397 ms 516 KB Output is correct
15 Correct 1441 ms 532 KB Output is correct
16 Correct 2319 ms 656 KB Output is correct
17 Correct 1588 ms 608 KB Output is correct
18 Correct 129 ms 204 KB Output is correct
19 Correct 961 ms 131568 KB Output is correct
20 Correct 982 ms 131396 KB Output is correct
21 Correct 999 ms 131556 KB Output is correct
22 Correct 952 ms 131428 KB Output is correct
23 Correct 942 ms 131436 KB Output is correct
24 Incorrect 73 ms 13392 KB Output isn't correct
25 Halted 0 ms 0 KB -