답안 #330932

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
330932	2020-11-26T23:03:04 Z	nvmdava	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1107 ms	103916 KB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1'000'005;
const ll MOD = 1'000'000'007;
const int INF = 0x3f3f3f3f;

int w[N], ans[N];
vector<int> t;
vector<pair<int, int> > v[N];
vector<pair<pair<int, int>, int> > q[N];

int fen[N];

int query(int r){
    int mx = 0;
    while(r){
        mx = max(mx, fen[r]);
        r -= r & -r;
    }
    return mx;
}

void update(int r, int x){
    while(r < N){
        fen[r] = max(fen[r], x);
        r += r & -r;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin>>n>>m;

    for(int i = 1; i <= n; ++i)
        cin>>w[i];

    for(int i = 1; i <= n; ++i){
        while(!t.empty() && w[t.back()] <= w[i])
            t.pop_back();
        if(!t.empty())
            v[t.back()].push_back({i, w[i] + w[t.back()]});
        t.push_back(i);
    }

    for(int i = 1; i <= m; ++i){
        int l, r, k;
        cin>>l>>r>>k;
        q[l].push_back({{r, k}, i});
    }

    for(int i = n; i > 0; --i){
        for(auto& x : v[i])
            update(x.ff, x.ss);
        for(auto& x : q[i])
            ans[x.ss] = (query(x.ff.ff) <= x.ff.ss);
    }
    for(int i = 1; i <= m; ++i)
        cout<<ans[i]<<'\n';
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	47340 KB	Output is correct
2	Correct	30 ms	47468 KB	Output is correct
3	Correct	31 ms	47340 KB	Output is correct
4	Correct	30 ms	47340 KB	Output is correct
5	Correct	31 ms	47340 KB	Output is correct
6	Correct	31 ms	47468 KB	Output is correct
7	Correct	33 ms	47468 KB	Output is correct
8	Correct	31 ms	47340 KB	Output is correct
9	Correct	31 ms	47340 KB	Output is correct
10	Correct	31 ms	47488 KB	Output is correct

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	47340 KB	Output is correct
2	Correct	30 ms	47468 KB	Output is correct
3	Correct	31 ms	47340 KB	Output is correct
4	Correct	30 ms	47340 KB	Output is correct
5	Correct	31 ms	47340 KB	Output is correct
6	Correct	31 ms	47468 KB	Output is correct
7	Correct	33 ms	47468 KB	Output is correct
8	Correct	31 ms	47340 KB	Output is correct
9	Correct	31 ms	47340 KB	Output is correct
10	Correct	31 ms	47488 KB	Output is correct
11	Correct	32 ms	47596 KB	Output is correct
12	Correct	33 ms	47636 KB	Output is correct
13	Correct	34 ms	47724 KB	Output is correct
14	Correct	34 ms	47852 KB	Output is correct
15	Correct	34 ms	47852 KB	Output is correct
16	Correct	33 ms	47724 KB	Output is correct
17	Correct	33 ms	47596 KB	Output is correct
18	Correct	34 ms	47596 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1067 ms	102880 KB	Output is correct
2	Correct	1083 ms	102892 KB	Output is correct
3	Correct	1084 ms	103020 KB	Output is correct
4	Correct	1069 ms	102892 KB	Output is correct
5	Correct	932 ms	82756 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	112 ms	54892 KB	Output is correct
2	Correct	98 ms	54636 KB	Output is correct
3	Correct	95 ms	52460 KB	Output is correct
4	Correct	95 ms	52540 KB	Output is correct
5	Correct	105 ms	52588 KB	Output is correct
6	Correct	82 ms	52076 KB	Output is correct
7	Correct	78 ms	51948 KB	Output is correct
8	Correct	110 ms	52712 KB	Output is correct
9	Correct	67 ms	50852 KB	Output is correct
10	Correct	88 ms	52584 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	47340 KB	Output is correct
2	Correct	30 ms	47468 KB	Output is correct
3	Correct	31 ms	47340 KB	Output is correct
4	Correct	30 ms	47340 KB	Output is correct
5	Correct	31 ms	47340 KB	Output is correct
6	Correct	31 ms	47468 KB	Output is correct
7	Correct	33 ms	47468 KB	Output is correct
8	Correct	31 ms	47340 KB	Output is correct
9	Correct	31 ms	47340 KB	Output is correct
10	Correct	31 ms	47488 KB	Output is correct
11	Correct	32 ms	47596 KB	Output is correct
12	Correct	33 ms	47636 KB	Output is correct
13	Correct	34 ms	47724 KB	Output is correct
14	Correct	34 ms	47852 KB	Output is correct
15	Correct	34 ms	47852 KB	Output is correct
16	Correct	33 ms	47724 KB	Output is correct
17	Correct	33 ms	47596 KB	Output is correct
18	Correct	34 ms	47596 KB	Output is correct
19	Correct	222 ms	64236 KB	Output is correct
20	Correct	233 ms	64236 KB	Output is correct
21	Correct	196 ms	63852 KB	Output is correct
22	Correct	191 ms	62744 KB	Output is correct
23	Correct	191 ms	63724 KB	Output is correct
24	Correct	162 ms	57708 KB	Output is correct
25	Correct	160 ms	58988 KB	Output is correct
26	Correct	183 ms	59116 KB	Output is correct
27	Correct	180 ms	59244 KB	Output is correct
28	Correct	188 ms	58988 KB	Output is correct
29	Correct	200 ms	59756 KB	Output is correct
30	Correct	198 ms	59756 KB	Output is correct
31	Correct	194 ms	59628 KB	Output is correct
32	Correct	204 ms	59756 KB	Output is correct
33	Correct	195 ms	59756 KB	Output is correct
34	Correct	146 ms	58348 KB	Output is correct
35	Correct	146 ms	58348 KB	Output is correct
36	Correct	143 ms	57196 KB	Output is correct
37	Correct	140 ms	58336 KB	Output is correct
38	Correct	149 ms	58092 KB	Output is correct
39	Correct	170 ms	59172 KB	Output is correct
40	Correct	160 ms	56496 KB	Output is correct
41	Correct	200 ms	58320 KB	Output is correct

Subtask #6
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	47340 KB	Output is correct
2	Correct	30 ms	47468 KB	Output is correct
3	Correct	31 ms	47340 KB	Output is correct
4	Correct	30 ms	47340 KB	Output is correct
5	Correct	31 ms	47340 KB	Output is correct
6	Correct	31 ms	47468 KB	Output is correct
7	Correct	33 ms	47468 KB	Output is correct
8	Correct	31 ms	47340 KB	Output is correct
9	Correct	31 ms	47340 KB	Output is correct
10	Correct	31 ms	47488 KB	Output is correct
11	Correct	32 ms	47596 KB	Output is correct
12	Correct	33 ms	47636 KB	Output is correct
13	Correct	34 ms	47724 KB	Output is correct
14	Correct	34 ms	47852 KB	Output is correct
15	Correct	34 ms	47852 KB	Output is correct
16	Correct	33 ms	47724 KB	Output is correct
17	Correct	33 ms	47596 KB	Output is correct
18	Correct	34 ms	47596 KB	Output is correct
19	Correct	1067 ms	102880 KB	Output is correct
20	Correct	1083 ms	102892 KB	Output is correct
21	Correct	1084 ms	103020 KB	Output is correct
22	Correct	1069 ms	102892 KB	Output is correct
23	Correct	932 ms	82756 KB	Output is correct
24	Correct	112 ms	54892 KB	Output is correct
25	Correct	98 ms	54636 KB	Output is correct
26	Correct	95 ms	52460 KB	Output is correct
27	Correct	95 ms	52540 KB	Output is correct
28	Correct	105 ms	52588 KB	Output is correct
29	Correct	82 ms	52076 KB	Output is correct
30	Correct	78 ms	51948 KB	Output is correct
31	Correct	110 ms	52712 KB	Output is correct
32	Correct	67 ms	50852 KB	Output is correct
33	Correct	88 ms	52584 KB	Output is correct
34	Correct	222 ms	64236 KB	Output is correct
35	Correct	233 ms	64236 KB	Output is correct
36	Correct	196 ms	63852 KB	Output is correct
37	Correct	191 ms	62744 KB	Output is correct
38	Correct	191 ms	63724 KB	Output is correct
39	Correct	162 ms	57708 KB	Output is correct
40	Correct	160 ms	58988 KB	Output is correct
41	Correct	183 ms	59116 KB	Output is correct
42	Correct	180 ms	59244 KB	Output is correct
43	Correct	188 ms	58988 KB	Output is correct
44	Correct	200 ms	59756 KB	Output is correct
45	Correct	198 ms	59756 KB	Output is correct
46	Correct	194 ms	59628 KB	Output is correct
47	Correct	204 ms	59756 KB	Output is correct
48	Correct	195 ms	59756 KB	Output is correct
49	Correct	146 ms	58348 KB	Output is correct
50	Correct	146 ms	58348 KB	Output is correct
51	Correct	143 ms	57196 KB	Output is correct
52	Correct	140 ms	58336 KB	Output is correct
53	Correct	149 ms	58092 KB	Output is correct
54	Correct	170 ms	59172 KB	Output is correct
55	Correct	160 ms	56496 KB	Output is correct
56	Correct	200 ms	58320 KB	Output is correct
57	Correct	1107 ms	103916 KB	Output is correct
58	Correct	1098 ms	103916 KB	Output is correct
59	Correct	1028 ms	102004 KB	Output is correct
60	Correct	1031 ms	101948 KB	Output is correct
61	Correct	1025 ms	101844 KB	Output is correct
62	Correct	1095 ms	102060 KB	Output is correct
63	Correct	663 ms	75244 KB	Output is correct
64	Correct	654 ms	75628 KB	Output is correct
65	Correct	910 ms	78956 KB	Output is correct
66	Correct	894 ms	78800 KB	Output is correct
67	Correct	892 ms	79468 KB	Output is correct
68	Correct	963 ms	81260 KB	Output is correct
69	Correct	954 ms	81388 KB	Output is correct
70	Correct	977 ms	80500 KB	Output is correct
71	Correct	942 ms	82924 KB	Output is correct
72	Correct	964 ms	80988 KB	Output is correct
73	Correct	591 ms	74520 KB	Output is correct
74	Correct	603 ms	74476 KB	Output is correct
75	Correct	602 ms	74788 KB	Output is correct
76	Correct	569 ms	74476 KB	Output is correct
77	Correct	573 ms	74404 KB	Output is correct
78	Correct	847 ms	84764 KB	Output is correct
79	Correct	646 ms	77272 KB	Output is correct
80	Correct	849 ms	89544 KB	Output is correct

답안 #330932

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