oj.uz

Submission #511534

# Submission time Handle Problem Language Result Execution time Memory
511534 2022-01-16T01:45:39 Z Gev2706 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 2415 ms 254656 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]]);
}
int query1(int& l, int& r, vector<vector<int>>& s) {
    return max(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);
    bool t = 1;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &w[i]); if (w[i] > 1000)t = 1;
    }
    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 if (t)
    {
        l2.resize(n + 2);
        l2[1] = 0;

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

        vector<vector<int>> st(n + 2, vector<int>(22));
        for (int i = 0; i < n; i++)
            st[i][0] = w[i];

        for (int j = 1; j <= 21; j++)
            for (int i = 0; i + (1 << j) <= n + 1; i++)
                st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        vector<vector<int>> inds(1005);
        for (int i = 0; i < n; i++) {
            inds[w[i]].push_back(i);
        }
        while (m--) {
            int l, r, k; scanf("%d%d%d", &l, &r, &k);
            l--, r--;
            if (k >= 2000) {
                printf("1\n");
                continue;
            }
            bool ttt = 1;
            for (int num = 0; num <= 1000; num++) {
                auto it = upper_bound(inds[num].begin(), inds[num].end(), r);
                if (it == inds[num].begin() || inds[num].size() == 0) {
                    continue;
                }
                it--;
                int ind = *it;
                ind--;
                if (ind >= l && ind <= r) {
                    if (query1(l, ind, st) + num > k) {
                        printf("0\n");
                        ttt = 1;
                        break;
                    }
                }

            }
            if (ttt) {
                printf("1\n");
            }
        }
    }
    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:42:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     int n, m; scanf("%d%d", &n, &m);
      |               ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d", &w[i]); if (w[i] > 1000)t = 1;
      |         ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:87:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |             int l, r, k; scanf("%d%d%d", &l, &r, &k);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:149:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |             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 292 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 12 ms 332 KB Output is correct
7 Correct 15 ms 332 KB Output is correct
8 Correct 18 ms 204 KB Output is correct
9 Correct 11 ms 300 KB Output is correct
10 Correct 4 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 292 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 12 ms 332 KB Output is correct
7 Correct 15 ms 332 KB Output is correct
8 Correct 18 ms 204 KB Output is correct
9 Correct 11 ms 300 KB Output is correct
10 Correct 4 ms 204 KB Output is correct
11 Correct 221 ms 428 KB Output is correct
12 Correct 758 ms 616 KB Output is correct
13 Correct 918 ms 628 KB Output is correct
14 Correct 1456 ms 672 KB Output is correct
15 Correct 1506 ms 676 KB Output is correct
16 Correct 2415 ms 636 KB Output is correct
17 Correct 1658 ms 588 KB Output is correct
18 Correct 147 ms 376 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 451 ms 254656 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1230 ms 15784 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 292 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 12 ms 332 KB Output is correct
7 Correct 15 ms 332 KB Output is correct
8 Correct 18 ms 204 KB Output is correct
9 Correct 11 ms 300 KB Output is correct
10 Correct 4 ms 204 KB Output is correct
11 Correct 221 ms 428 KB Output is correct
12 Correct 758 ms 616 KB Output is correct
13 Correct 918 ms 628 KB Output is correct
14 Correct 1456 ms 672 KB Output is correct
15 Correct 1506 ms 676 KB Output is correct
16 Correct 2415 ms 636 KB Output is correct
17 Correct 1658 ms 588 KB Output is correct
18 Correct 147 ms 376 KB Output is correct
19 Runtime error 86 ms 51920 KB Execution killed with signal 11
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 292 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 12 ms 332 KB Output is correct
7 Correct 15 ms 332 KB Output is correct
8 Correct 18 ms 204 KB Output is correct
9 Correct 11 ms 300 KB Output is correct
10 Correct 4 ms 204 KB Output is correct
11 Correct 221 ms 428 KB Output is correct
12 Correct 758 ms 616 KB Output is correct
13 Correct 918 ms 628 KB Output is correct
14 Correct 1456 ms 672 KB Output is correct
15 Correct 1506 ms 676 KB Output is correct
16 Correct 2415 ms 636 KB Output is correct
17 Correct 1658 ms 588 KB Output is correct
18 Correct 147 ms 376 KB Output is correct
19 Runtime error 451 ms 254656 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -