oj.uz

답안 #655191

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
655191 2022-11-03T14:04:28 Z stevancv Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
8 / 100
 3000 ms 29004 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e6 + 2;
const int inf = 2e9;
struct node {
    int mx, mn, ans;
}st[4 * N];
int arr[N];
node Merge(node a, node b) {
    node c;
    c.ans = max(a.ans, b.ans);
    if (a.mx > b.mn) smax(c.ans, a.mx + b.mn);
    c.mx = max(a.mx, b.mx);
    c.mn = min(a.mn, b.mn);
    return c;
}
void Init(int node, int l, int r) {
    if (l == r) {
        st[node] = {arr[l], arr[l] + 1, 0};
        return;
    }
    int mid = l + r >> 1;
    Init(2 * node, l, mid);
    Init(2 * node + 1, mid + 1, r);
    st[node] = Merge(st[2 * node], st[2 * node + 1]);
}
node Get(int node, int l, int r, int ql, int qr) {
    if (r < ql || qr < l) return {-inf, inf, 0};
    if (ql <= l && r <= qr) return st[node];
    int mid = l + r >> 1;
    return Merge(Get(2 * node, l, mid, ql, qr), Get(2 * node + 1, mid + 1, r, ql, qr));
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> arr[i];
    Init(1, 0, n - 1);
    while (m--) {
        int l, r, x;
        cin >> l >> r >> x;
        l -= 1; r -= 1;
        int ans = 0;
        for (int i = l; i <= r; i++) {
            for (int j = i + 1; j <= r; j++) {
                if (arr[i] > arr[j]) smax(ans, arr[i] + arr[j]);
            }
        }
        if (ans <= x) cout << 1 << en;
        else cout << 0 << en;
        /*node ans = Get(1, 0, n - 1, l, r);
        if (ans.ans <= x) cout << 1 << en;
        else cout << 0 << en;*/
    }
    return 0;
}

Compilation message

sortbooks.cpp: In function 'void Init(int, int, int)':
sortbooks.cpp:28:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |     int mid = l + r >> 1;
      |               ~~^~~
sortbooks.cpp: In function 'node Get(int, int, int, int, int)':
sortbooks.cpp:36:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 24 ms 368 KB Output is correct
7 Correct 25 ms 340 KB Output is correct
8 Correct 36 ms 344 KB Output is correct
9 Correct 11 ms 340 KB Output is correct
10 Correct 27 ms 340 KB Output is correct

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 24 ms 368 KB Output is correct
7 Correct 25 ms 340 KB Output is correct
8 Correct 36 ms 344 KB Output is correct
9 Correct 11 ms 340 KB Output is correct
10 Correct 27 ms 340 KB Output is correct
11 Correct 1235 ms 456 KB Output is correct
12 Execution timed out 3069 ms 724 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3061 ms 29004 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3085 ms 4400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 24 ms 368 KB Output is correct
7 Correct 25 ms 340 KB Output is correct
8 Correct 36 ms 344 KB Output is correct
9 Correct 11 ms 340 KB Output is correct
10 Correct 27 ms 340 KB Output is correct
11 Correct 1235 ms 456 KB Output is correct
12 Execution timed out 3069 ms 724 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 24 ms 368 KB Output is correct
7 Correct 25 ms 340 KB Output is correct
8 Correct 36 ms 344 KB Output is correct
9 Correct 11 ms 340 KB Output is correct
10 Correct 27 ms 340 KB Output is correct
11 Correct 1235 ms 456 KB Output is correct
12 Execution timed out 3069 ms 724 KB Time limit exceeded
13 Halted 0 ms 0 KB -