oj.uz

Submission #511539

# Submission time Handle Problem Language Result Execution time Memory
511539 2022-01-16T01:48:40 Z Gev2706 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
30 / 100
 2338 ms 133664 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 = 0;
    }
    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++) {
                if (inds[num].empty())continue;
                auto it = upper_bound(inds[num].begin(), inds[num].end(), r);
                if (it == inds[num].begin()) {
                    continue;
                }
                it--;
                int ind = *it;
                ind--;
                if (ind >= l && ind <= r) {
                    if (query1(l, ind, st) + num > k) {
                        printf("0\n");
                        ttt = 0;
                        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 = 0;
      |         ~~~~~^~~~~~~~~~~~~
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:150:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |             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 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 12 ms 204 KB Output is correct
7 Correct 12 ms 204 KB Output is correct
8 Correct 18 ms 204 KB Output is correct
9 Correct 9 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 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 12 ms 204 KB Output is correct
7 Correct 12 ms 204 KB Output is correct
8 Correct 18 ms 204 KB Output is correct
9 Correct 9 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 233 ms 348 KB Output is correct
12 Correct 734 ms 512 KB Output is correct
13 Correct 869 ms 524 KB Output is correct
14 Correct 1409 ms 532 KB Output is correct
15 Correct 1465 ms 520 KB Output is correct
16 Correct 2338 ms 524 KB Output is correct
17 Correct 1676 ms 488 KB Output is correct
18 Correct 126 ms 292 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 996 ms 133492 KB Output is correct
2 Correct 1016 ms 133664 KB Output is correct
3 Correct 1065 ms 131840 KB Output is correct
4 Correct 1018 ms 131912 KB Output is correct
5 Correct 1065 ms 132004 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1501 ms 13600 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 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 12 ms 204 KB Output is correct
7 Correct 12 ms 204 KB Output is correct
8 Correct 18 ms 204 KB Output is correct
9 Correct 9 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 233 ms 348 KB Output is correct
12 Correct 734 ms 512 KB Output is correct
13 Correct 869 ms 524 KB Output is correct
14 Correct 1409 ms 532 KB Output is correct
15 Correct 1465 ms 520 KB Output is correct
16 Correct 2338 ms 524 KB Output is correct
17 Correct 1676 ms 488 KB Output is correct
18 Correct 126 ms 292 KB Output is correct
19 Incorrect 244 ms 28552 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 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 12 ms 204 KB Output is correct
7 Correct 12 ms 204 KB Output is correct
8 Correct 18 ms 204 KB Output is correct
9 Correct 9 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 233 ms 348 KB Output is correct
12 Correct 734 ms 512 KB Output is correct
13 Correct 869 ms 524 KB Output is correct
14 Correct 1409 ms 532 KB Output is correct
15 Correct 1465 ms 520 KB Output is correct
16 Correct 2338 ms 524 KB Output is correct
17 Correct 1676 ms 488 KB Output is correct
18 Correct 126 ms 292 KB Output is correct
19 Correct 996 ms 133492 KB Output is correct
20 Correct 1016 ms 133664 KB Output is correct
21 Correct 1065 ms 131840 KB Output is correct
22 Correct 1018 ms 131912 KB Output is correct
23 Correct 1065 ms 132004 KB Output is correct
24 Incorrect 1501 ms 13600 KB Output isn't correct
25 Halted 0 ms 0 KB -