Submission #651380

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
651380	2022-10-18T15:57:09 Z	Astrayt	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	664 ms	63172 KB

sortbooks

//君の手を握ってしまったら
//孤独を知らないこの街には
//もう二度と帰ってくることはできないのでしょう
//君が手を差し伸べた 光で影が生まれる
//歌って聞かせて この話の続き
//連れて行って見たことない星まで
//さユリ - 花の塔
#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 = 1000004, val[1000005];
    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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 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	340 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 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	340 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 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	596 KB	Output is correct
14	Correct	4 ms	728 KB	Output is correct
15	Correct	4 ms	724 KB	Output is correct
16	Correct	3 ms	724 KB	Output is correct
17	Correct	3 ms	592 KB	Output is correct
18	Correct	4 ms	612 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	582 ms	57548 KB	Output is correct
2	Correct	654 ms	57784 KB	Output is correct
3	Correct	597 ms	57616 KB	Output is correct
4	Correct	603 ms	57884 KB	Output is correct
5	Correct	581 ms	59952 KB	Output is correct

Subtask #4
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	6176 KB	Output is correct
2	Correct	49 ms	6184 KB	Output is correct
3	Correct	49 ms	5416 KB	Output is correct
4	Correct	48 ms	5408 KB	Output is correct
5	Correct	47 ms	5416 KB	Output is correct
6	Correct	43 ms	5416 KB	Output is correct
7	Correct	48 ms	5416 KB	Output is correct
8	Correct	46 ms	5452 KB	Output is correct
9	Correct	40 ms	4640 KB	Output is correct
10	Correct	46 ms	5428 KB	Output is correct

Subtask #5
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 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	340 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 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	596 KB	Output is correct
14	Correct	4 ms	728 KB	Output is correct
15	Correct	4 ms	724 KB	Output is correct
16	Correct	3 ms	724 KB	Output is correct
17	Correct	3 ms	592 KB	Output is correct
18	Correct	4 ms	612 KB	Output is correct
19	Correct	128 ms	11876 KB	Output is correct
20	Correct	136 ms	11928 KB	Output is correct
21	Correct	116 ms	11856 KB	Output is correct
22	Correct	114 ms	11980 KB	Output is correct
23	Correct	123 ms	11888 KB	Output is correct
24	Correct	108 ms	10384 KB	Output is correct
25	Correct	104 ms	10316 KB	Output is correct
26	Correct	111 ms	10360 KB	Output is correct
27	Correct	116 ms	10360 KB	Output is correct
28	Correct	110 ms	10376 KB	Output is correct
29	Correct	107 ms	10356 KB	Output is correct
30	Correct	109 ms	10356 KB	Output is correct
31	Correct	109 ms	10360 KB	Output is correct
32	Correct	108 ms	10356 KB	Output is correct
33	Correct	113 ms	10360 KB	Output is correct
34	Correct	104 ms	10376 KB	Output is correct
35	Correct	107 ms	10352 KB	Output is correct
36	Correct	101 ms	10376 KB	Output is correct
37	Correct	103 ms	10332 KB	Output is correct
38	Correct	104 ms	10372 KB	Output is correct
39	Correct	96 ms	10872 KB	Output is correct
40	Correct	89 ms	9840 KB	Output is correct
41	Correct	108 ms	10316 KB	Output is correct

Subtask #6
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 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	340 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 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	596 KB	Output is correct
14	Correct	4 ms	728 KB	Output is correct
15	Correct	4 ms	724 KB	Output is correct
16	Correct	3 ms	724 KB	Output is correct
17	Correct	3 ms	592 KB	Output is correct
18	Correct	4 ms	612 KB	Output is correct
19	Correct	582 ms	57548 KB	Output is correct
20	Correct	654 ms	57784 KB	Output is correct
21	Correct	597 ms	57616 KB	Output is correct
22	Correct	603 ms	57884 KB	Output is correct
23	Correct	581 ms	59952 KB	Output is correct
24	Correct	49 ms	6176 KB	Output is correct
25	Correct	49 ms	6184 KB	Output is correct
26	Correct	49 ms	5416 KB	Output is correct
27	Correct	48 ms	5408 KB	Output is correct
28	Correct	47 ms	5416 KB	Output is correct
29	Correct	43 ms	5416 KB	Output is correct
30	Correct	48 ms	5416 KB	Output is correct
31	Correct	46 ms	5452 KB	Output is correct
32	Correct	40 ms	4640 KB	Output is correct
33	Correct	46 ms	5428 KB	Output is correct
34	Correct	128 ms	11876 KB	Output is correct
35	Correct	136 ms	11928 KB	Output is correct
36	Correct	116 ms	11856 KB	Output is correct
37	Correct	114 ms	11980 KB	Output is correct
38	Correct	123 ms	11888 KB	Output is correct
39	Correct	108 ms	10384 KB	Output is correct
40	Correct	104 ms	10316 KB	Output is correct
41	Correct	111 ms	10360 KB	Output is correct
42	Correct	116 ms	10360 KB	Output is correct
43	Correct	110 ms	10376 KB	Output is correct
44	Correct	107 ms	10356 KB	Output is correct
45	Correct	109 ms	10356 KB	Output is correct
46	Correct	109 ms	10360 KB	Output is correct
47	Correct	108 ms	10356 KB	Output is correct
48	Correct	113 ms	10360 KB	Output is correct
49	Correct	104 ms	10376 KB	Output is correct
50	Correct	107 ms	10352 KB	Output is correct
51	Correct	101 ms	10376 KB	Output is correct
52	Correct	103 ms	10332 KB	Output is correct
53	Correct	104 ms	10372 KB	Output is correct
54	Correct	96 ms	10872 KB	Output is correct
55	Correct	89 ms	9840 KB	Output is correct
56	Correct	108 ms	10316 KB	Output is correct
57	Correct	664 ms	63052 KB	Output is correct
58	Correct	628 ms	63072 KB	Output is correct
59	Correct	601 ms	63172 KB	Output is correct
60	Correct	601 ms	63044 KB	Output is correct
61	Correct	601 ms	63036 KB	Output is correct
62	Correct	598 ms	63092 KB	Output is correct
63	Correct	549 ms	54652 KB	Output is correct
64	Correct	530 ms	54780 KB	Output is correct
65	Correct	549 ms	55056 KB	Output is correct
66	Correct	545 ms	55020 KB	Output is correct
67	Correct	555 ms	55000 KB	Output is correct
68	Correct	570 ms	55056 KB	Output is correct
69	Correct	582 ms	55124 KB	Output is correct
70	Correct	553 ms	54872 KB	Output is correct
71	Correct	555 ms	52996 KB	Output is correct
72	Correct	540 ms	53180 KB	Output is correct
73	Correct	511 ms	52720 KB	Output is correct
74	Correct	562 ms	52780 KB	Output is correct
75	Correct	608 ms	52712 KB	Output is correct
76	Correct	511 ms	51208 KB	Output is correct
77	Correct	529 ms	50452 KB	Output is correct
78	Correct	531 ms	52588 KB	Output is correct
79	Correct	432 ms	46092 KB	Output is correct
80	Correct	498 ms	49884 KB	Output is correct

Submission #651380

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 9.0 / 9.0

Subtask #3 13.0 / 13.0

Subtask #4 17.0 / 17.0

Subtask #5 30.0 / 30.0

Subtask #6 23.0 / 23.0

Subtask #1
8.0 / 8.0

Subtask #2
9.0 / 9.0

Subtask #3
13.0 / 13.0

Subtask #4
17.0 / 17.0

Subtask #5
30.0 / 30.0

Subtask #6
23.0 / 23.0