oj.uz

답안 #511475

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
511475 2022-01-16T00:04:23 Z Gev2706 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 2283 ms 262144 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

int query(int l, int r, vector<vector<int>> &s) {
    int t = r - l + 1;
    t = log2(t);
    return min(s[l][t], s[r - (1 << t) + 1][t]);
}

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]) {
                v[st.top()] = w[i];
                st.pop();
            }
            st.push(i);
        }
        while (!st.empty())
        {
            v[st.top()] = -1;
            st.pop();
        }
        vector<vector<int>> sp(n + 5, vector<int>(30, 0));
        for (int i = 0; i < n; i++)sp[i][0] = v[i];
        for (int i = 0; i < n; i++) {
            for (int j = 1; j + (1 << i) < n; j++)
                sp[i][j] = min(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
        }

        while (m--) {
            int l, r; cin >> l >> r;
            l--, r--;
            cout << query(l, r, sp) << endl;
        }
    }
}
int main()
{
    //int tc; cin >> tc;while(tc--)
    solve();
    return 0;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 288 KB Output is correct
2 Correct 0 ms 292 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 12 ms 204 KB Output is correct
7 Correct 12 ms 304 KB Output is correct
8 Correct 18 ms 204 KB Output is correct
9 Correct 8 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 288 KB Output is correct
2 Correct 0 ms 292 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 12 ms 204 KB Output is correct
7 Correct 12 ms 304 KB Output is correct
8 Correct 18 ms 204 KB Output is correct
9 Correct 8 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 214 ms 420 KB Output is correct
12 Correct 719 ms 624 KB Output is correct
13 Correct 823 ms 580 KB Output is correct
14 Correct 1380 ms 668 KB Output is correct
15 Correct 1407 ms 552 KB Output is correct
16 Correct 2283 ms 632 KB Output is correct
17 Correct 1609 ms 588 KB Output is correct
18 Correct 122 ms 300 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 618 ms 262144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 44 ms 32708 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 288 KB Output is correct
2 Correct 0 ms 292 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 12 ms 204 KB Output is correct
7 Correct 12 ms 304 KB Output is correct
8 Correct 18 ms 204 KB Output is correct
9 Correct 8 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 214 ms 420 KB Output is correct
12 Correct 719 ms 624 KB Output is correct
13 Correct 823 ms 580 KB Output is correct
14 Correct 1380 ms 668 KB Output is correct
15 Correct 1407 ms 552 KB Output is correct
16 Correct 2283 ms 632 KB Output is correct
17 Correct 1609 ms 588 KB Output is correct
18 Correct 122 ms 300 KB Output is correct
19 Runtime error 119 ms 63816 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 288 KB Output is correct
2 Correct 0 ms 292 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 12 ms 204 KB Output is correct
7 Correct 12 ms 304 KB Output is correct
8 Correct 18 ms 204 KB Output is correct
9 Correct 8 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 214 ms 420 KB Output is correct
12 Correct 719 ms 624 KB Output is correct
13 Correct 823 ms 580 KB Output is correct
14 Correct 1380 ms 668 KB Output is correct
15 Correct 1407 ms 552 KB Output is correct
16 Correct 2283 ms 632 KB Output is correct
17 Correct 1609 ms 588 KB Output is correct
18 Correct 122 ms 300 KB Output is correct
19 Runtime error 618 ms 262144 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -