oj.uz

답안 #651378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
651378 2022-10-18T15:56:12 Z Astrayt Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 563 ms 111068 KB 
//君の手を握ってしまったら
//孤独を知らないこの街には
//もう二度と帰ってくることはできないのでしょう
//君が手を差し伸べた 光で影が生まれる
//歌って聞かせて この話の続き
//連れて行って見たことない星まで
//さユリ - 花の塔
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define starburst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pii pair<int,int>
#define pb push_back
#define ff first
#define ss second

struct FenwickTree{
    int n = 200005, val[200005];
    void modify(int p, int x){
        for(; p; p -= p&-p) val[p] = max(x, val[p]);
    }
    int query(int p){
        int ret = 0;
        for(; p < n; p += p&-p) ret = max(ret, val[p]);
        return ret;
    }
}BIT;

struct qry{
    int l, r, k, i;
};

void solve(){
    int n, m; cin >> n >> m;
    vector<int> w(n + 1, 0), ans(m + 1, 0);
    for(int i = 1; i <= n; ++i) cin >> w[i];
    vector<qry> Q(m + 1);
    for(int i = 1; i <= m; ++i){
        auto &[l, r, k, ind] = Q[i];
        cin >> l >> r >> k;
        ind = i;
    }
    sort(Q.begin() + 1, Q.end(), [](qry q1, qry q2){return q1.r < q2.r;});
    stack<int> stk;
    for(int i = 1, j = 1; i <= n; ++i){
        while(stk.size() && w[stk.top()] <= w[i]) stk.pop();
        if(stk.size()) BIT.modify(stk.top(), w[stk.top()] + w[i]);
        while(j <= m && Q[j].r == i){
            if(Q[j].k >= BIT.query(Q[j].l)){
                ans[Q[j].i] = 1;
            }
            j++;
        }
        stk.push(i);
    }
    for(int i = 1; i <= m; ++i) cout << ans[i] << '\n';
}

signed main(){
    starburst
    int t = 1; //cin >> t;
    while(t--) solve();
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 3 ms 624 KB Output is correct
14 Correct 4 ms 724 KB Output is correct
15 Correct 3 ms 728 KB Output is correct
16 Correct 3 ms 592 KB Output is correct
17 Correct 4 ms 596 KB Output is correct
18 Correct 3 ms 596 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 7884 KB Output is correct
2 Correct 54 ms 7864 KB Output is correct
3 Correct 62 ms 7184 KB Output is correct
4 Correct 52 ms 7116 KB Output is correct
5 Correct 49 ms 7180 KB Output is correct
6 Correct 46 ms 7064 KB Output is correct
7 Correct 46 ms 7008 KB Output is correct
8 Correct 52 ms 6860 KB Output is correct
9 Correct 41 ms 5708 KB Output is correct
10 Correct 47 ms 6860 KB Output is correct

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 3 ms 624 KB Output is correct
14 Correct 4 ms 724 KB Output is correct
15 Correct 3 ms 728 KB Output is correct
16 Correct 3 ms 592 KB Output is correct
17 Correct 4 ms 596 KB Output is correct
18 Correct 3 ms 596 KB Output is correct
19 Correct 128 ms 18260 KB Output is correct
20 Correct 130 ms 18220 KB Output is correct
21 Correct 117 ms 17996 KB Output is correct
22 Correct 128 ms 18016 KB Output is correct
23 Correct 167 ms 18124 KB Output is correct
24 Correct 112 ms 16416 KB Output is correct
25 Correct 151 ms 16332 KB Output is correct
26 Correct 123 ms 16612 KB Output is correct
27 Correct 122 ms 16592 KB Output is correct
28 Correct 137 ms 16620 KB Output is correct
29 Correct 120 ms 16692 KB Output is correct
30 Correct 120 ms 16632 KB Output is correct
31 Correct 117 ms 16664 KB Output is correct
32 Correct 133 ms 16616 KB Output is correct
33 Correct 124 ms 16588 KB Output is correct
34 Correct 133 ms 16320 KB Output is correct
35 Correct 127 ms 16296 KB Output is correct
36 Correct 117 ms 16104 KB Output is correct
37 Correct 127 ms 16108 KB Output is correct
38 Correct 119 ms 16256 KB Output is correct
39 Correct 113 ms 15820 KB Output is correct
40 Correct 99 ms 14028 KB Output is correct
41 Correct 103 ms 14816 KB Output is correct

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 3 ms 624 KB Output is correct
14 Correct 4 ms 724 KB Output is correct
15 Correct 3 ms 728 KB Output is correct
16 Correct 3 ms 592 KB Output is correct
17 Correct 4 ms 596 KB Output is correct
18 Correct 3 ms 596 KB Output is correct
19 Runtime error 563 ms 111068 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -