oj.uz

Submission #511506

# Submission time Handle Problem Language Result Execution time Memory
511506 2022-01-16T00:51:02 Z Gev2706 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 2924 ms 131900 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; 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, vector<int>(21, 0));
        for (int i = 0; i < n; i++)sp[i][0] = v[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) {
                printf("0\n");
            }
            else printf("1\n");
        }
    }
}
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;
}

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]);
      |                                ~~~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 4 ms 4252 KB Output is correct
5 Correct 4 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 20 ms 4224 KB Output is correct
9 Correct 14 ms 4172 KB Output is correct
10 Correct 5 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 3 ms 4172 KB Output is correct
3 Correct 6 ms 4172 KB Output is correct
4 Correct 4 ms 4252 KB Output is correct
5 Correct 4 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 20 ms 4224 KB Output is correct
9 Correct 14 ms 4172 KB Output is correct
10 Correct 5 ms 4172 KB Output is correct
11 Correct 220 ms 4300 KB Output is correct
12 Correct 733 ms 4604 KB Output is correct
13 Correct 852 ms 4548 KB Output is correct
14 Correct 1471 ms 4612 KB Output is correct
15 Correct 1474 ms 4560 KB Output is correct
16 Correct 2371 ms 4532 KB Output is correct
17 Correct 1642 ms 4476 KB Output is correct
18 Correct 123 ms 4172 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2743 ms 131684 KB Output is correct
2 Correct 2828 ms 131636 KB Output is correct
3 Correct 2821 ms 131732 KB Output is correct
4 Correct 2924 ms 131888 KB Output is correct
5 Incorrect 2910 ms 131900 KB Output isn't correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 268 ms 17976 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 3 ms 4172 KB Output is correct
3 Correct 6 ms 4172 KB Output is correct
4 Correct 4 ms 4252 KB Output is correct
5 Correct 4 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 20 ms 4224 KB Output is correct
9 Correct 14 ms 4172 KB Output is correct
10 Correct 5 ms 4172 KB Output is correct
11 Correct 220 ms 4300 KB Output is correct
12 Correct 733 ms 4604 KB Output is correct
13 Correct 852 ms 4548 KB Output is correct
14 Correct 1471 ms 4612 KB Output is correct
15 Correct 1474 ms 4560 KB Output is correct
16 Correct 2371 ms 4532 KB Output is correct
17 Correct 1642 ms 4476 KB Output is correct
18 Correct 123 ms 4172 KB Output is correct
19 Incorrect 671 ms 32244 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 3 ms 4172 KB Output is correct
3 Correct 6 ms 4172 KB Output is correct
4 Correct 4 ms 4252 KB Output is correct
5 Correct 4 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 20 ms 4224 KB Output is correct
9 Correct 14 ms 4172 KB Output is correct
10 Correct 5 ms 4172 KB Output is correct
11 Correct 220 ms 4300 KB Output is correct
12 Correct 733 ms 4604 KB Output is correct
13 Correct 852 ms 4548 KB Output is correct
14 Correct 1471 ms 4612 KB Output is correct
15 Correct 1474 ms 4560 KB Output is correct
16 Correct 2371 ms 4532 KB Output is correct
17 Correct 1642 ms 4476 KB Output is correct
18 Correct 123 ms 4172 KB Output is correct
19 Correct 2743 ms 131684 KB Output is correct
20 Correct 2828 ms 131636 KB Output is correct
21 Correct 2821 ms 131732 KB Output is correct
22 Correct 2924 ms 131888 KB Output is correct
23 Incorrect 2910 ms 131900 KB Output isn't correct