답안 #793899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
793899	2023-07-26T07:55:15 Z	12345678	Pilot (NOI19_pilot)	C++17	100 / 100	991 ms	87956 KB

pilot

#include <bits/stdc++.h>

using namespace std;

const int nx=1e6+5;
long long n, q, h[nx], dp[nx], t, l, r;
vector<vector<int>> d(nx);

struct segtree
{
    int d[4*nx];
    void build(int l, int r, int i)
    {
        if (l==r) return void(d[i]=h[l]);
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    int queryleft(int l, int r, int i, int idx)
    {
        if (idx<=l) return -1;
        if (l==r&&d[i]>h[idx]) return l;
        if (d[i]<=h[idx]) return -1;
        int md=(l+r)/2, tmp=queryleft(md+1, r, 2*i+1, idx);
        if (tmp!=-1) return tmp;
        return queryleft(l, md, 2*i, idx);
    }
    int queryright(int l, int r, int i, int idx)
    {
        if (idx>=r) return -1;
        if (l==r&&d[i]>=h[idx]) return l;
        if (d[i]<h[idx]) return -1;
        int md=(l+r)/2, tmp=queryright(l, md, 2*i, idx);
        if (tmp!=-1) return tmp;
        return queryright(md+1, r, 2*i+1, idx);
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q;
    for (int i=1; i<=n; i++) cin>>h[i], d[h[i]].push_back(i);
    s.build(1, n, 1);
    for (int i=1; i<nx; i++)
    {
        dp[i]=dp[i-1];
        sort(d[i].begin(), d[i].end());
        for (auto x:d[i])
        {
            l=1; r=n;
            int left=s.queryleft(1, n, 1, x), right=s.queryright(1, n, 1, x);
            if (left!=-1) l=left+1;
            if (right!=-1) r=right-1;
            dp[i]+=(x-l+1)*(r-x+1);
            //cout<<i<<' '<<l<<' '<<r<<' '<<x<<' '<<dp[i]<<' '<<left<<' '<<right<<'\n';
        }
    }
    //cout<<s.queryright(1, n, 1, 1);
    while (q--) cin>>t, cout<<dp[t]<<'\n';
}

Subtask #1
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	31572 KB	Output is correct
2	Correct	17 ms	31572 KB	Output is correct
3	Correct	20 ms	31584 KB	Output is correct
4	Correct	17 ms	31564 KB	Output is correct
5	Correct	17 ms	31556 KB	Output is correct
6	Correct	18 ms	31652 KB	Output is correct
7	Correct	20 ms	31632 KB	Output is correct
8	Correct	20 ms	31612 KB	Output is correct
9	Correct	19 ms	31548 KB	Output is correct
10	Correct	20 ms	31572 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	31572 KB	Output is correct
2	Correct	17 ms	31572 KB	Output is correct
3	Correct	20 ms	31584 KB	Output is correct
4	Correct	17 ms	31564 KB	Output is correct
5	Correct	17 ms	31556 KB	Output is correct
6	Correct	18 ms	31652 KB	Output is correct
7	Correct	20 ms	31632 KB	Output is correct
8	Correct	20 ms	31612 KB	Output is correct
9	Correct	19 ms	31548 KB	Output is correct
10	Correct	20 ms	31572 KB	Output is correct
11	Correct	18 ms	31548 KB	Output is correct
12	Correct	19 ms	31628 KB	Output is correct
13	Correct	17 ms	31636 KB	Output is correct
14	Correct	18 ms	31572 KB	Output is correct
15	Correct	20 ms	31532 KB	Output is correct

Subtask #3
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	31572 KB	Output is correct
2	Correct	17 ms	31572 KB	Output is correct
3	Correct	20 ms	31584 KB	Output is correct
4	Correct	17 ms	31564 KB	Output is correct
5	Correct	17 ms	31556 KB	Output is correct
6	Correct	18 ms	31652 KB	Output is correct
7	Correct	20 ms	31632 KB	Output is correct
8	Correct	20 ms	31612 KB	Output is correct
9	Correct	19 ms	31548 KB	Output is correct
10	Correct	20 ms	31572 KB	Output is correct
11	Correct	18 ms	31548 KB	Output is correct
12	Correct	19 ms	31628 KB	Output is correct
13	Correct	17 ms	31636 KB	Output is correct
14	Correct	18 ms	31572 KB	Output is correct
15	Correct	20 ms	31532 KB	Output is correct
16	Correct	18 ms	31644 KB	Output is correct
17	Correct	21 ms	31644 KB	Output is correct
18	Correct	17 ms	31568 KB	Output is correct
19	Correct	18 ms	31572 KB	Output is correct
20	Correct	18 ms	31572 KB	Output is correct

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	31572 KB	Output is correct
2	Correct	17 ms	31572 KB	Output is correct
3	Correct	20 ms	31584 KB	Output is correct
4	Correct	17 ms	31564 KB	Output is correct
5	Correct	17 ms	31556 KB	Output is correct
6	Correct	18 ms	31652 KB	Output is correct
7	Correct	20 ms	31632 KB	Output is correct
8	Correct	20 ms	31612 KB	Output is correct
9	Correct	19 ms	31548 KB	Output is correct
10	Correct	20 ms	31572 KB	Output is correct
11	Correct	18 ms	31548 KB	Output is correct
12	Correct	19 ms	31628 KB	Output is correct
13	Correct	17 ms	31636 KB	Output is correct
14	Correct	18 ms	31572 KB	Output is correct
15	Correct	20 ms	31532 KB	Output is correct
16	Correct	18 ms	31644 KB	Output is correct
17	Correct	21 ms	31644 KB	Output is correct
18	Correct	17 ms	31568 KB	Output is correct
19	Correct	18 ms	31572 KB	Output is correct
20	Correct	18 ms	31572 KB	Output is correct
21	Correct	19 ms	31704 KB	Output is correct
22	Correct	19 ms	31700 KB	Output is correct
23	Correct	21 ms	31608 KB	Output is correct
24	Correct	20 ms	31592 KB	Output is correct
25	Correct	19 ms	31640 KB	Output is correct

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	58 ms	35272 KB	Output is correct
2	Correct	72 ms	36296 KB	Output is correct
3	Correct	63 ms	35176 KB	Output is correct
4	Correct	70 ms	36028 KB	Output is correct
5	Correct	60 ms	35148 KB	Output is correct

Subtask #6
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	37572 KB	Output is correct
2	Correct	57 ms	38480 KB	Output is correct
3	Correct	57 ms	38312 KB	Output is correct
4	Correct	60 ms	38560 KB	Output is correct
5	Correct	60 ms	38276 KB	Output is correct

Subtask #7
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	37696 KB	Output is correct
2	Correct	74 ms	38464 KB	Output is correct
3	Correct	69 ms	38460 KB	Output is correct
4	Correct	65 ms	38716 KB	Output is correct
5	Correct	86 ms	38604 KB	Output is correct

Subtask #8
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	31572 KB	Output is correct
2	Correct	17 ms	31572 KB	Output is correct
3	Correct	20 ms	31584 KB	Output is correct
4	Correct	17 ms	31564 KB	Output is correct
5	Correct	17 ms	31556 KB	Output is correct
6	Correct	18 ms	31652 KB	Output is correct
7	Correct	20 ms	31632 KB	Output is correct
8	Correct	20 ms	31612 KB	Output is correct
9	Correct	19 ms	31548 KB	Output is correct
10	Correct	20 ms	31572 KB	Output is correct
11	Correct	58 ms	35272 KB	Output is correct
12	Correct	72 ms	36296 KB	Output is correct
13	Correct	63 ms	35176 KB	Output is correct
14	Correct	70 ms	36028 KB	Output is correct
15	Correct	60 ms	35148 KB	Output is correct
16	Correct	59 ms	35224 KB	Output is correct
17	Correct	72 ms	36308 KB	Output is correct
18	Correct	74 ms	36384 KB	Output is correct
19	Correct	60 ms	35184 KB	Output is correct
20	Correct	102 ms	36260 KB	Output is correct
21	Correct	56 ms	35148 KB	Output is correct
22	Correct	69 ms	36060 KB	Output is correct
23	Correct	58 ms	35404 KB	Output is correct
24	Correct	66 ms	36016 KB	Output is correct
25	Correct	59 ms	35276 KB	Output is correct

Subtask #9
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	31572 KB	Output is correct
2	Correct	17 ms	31572 KB	Output is correct
3	Correct	20 ms	31584 KB	Output is correct
4	Correct	17 ms	31564 KB	Output is correct
5	Correct	17 ms	31556 KB	Output is correct
6	Correct	18 ms	31652 KB	Output is correct
7	Correct	20 ms	31632 KB	Output is correct
8	Correct	20 ms	31612 KB	Output is correct
9	Correct	19 ms	31548 KB	Output is correct
10	Correct	20 ms	31572 KB	Output is correct
11	Correct	18 ms	31548 KB	Output is correct
12	Correct	19 ms	31628 KB	Output is correct
13	Correct	17 ms	31636 KB	Output is correct
14	Correct	18 ms	31572 KB	Output is correct
15	Correct	20 ms	31532 KB	Output is correct
16	Correct	18 ms	31644 KB	Output is correct
17	Correct	21 ms	31644 KB	Output is correct
18	Correct	17 ms	31568 KB	Output is correct
19	Correct	18 ms	31572 KB	Output is correct
20	Correct	18 ms	31572 KB	Output is correct
21	Correct	19 ms	31704 KB	Output is correct
22	Correct	19 ms	31700 KB	Output is correct
23	Correct	21 ms	31608 KB	Output is correct
24	Correct	20 ms	31592 KB	Output is correct
25	Correct	19 ms	31640 KB	Output is correct
26	Correct	58 ms	35272 KB	Output is correct
27	Correct	72 ms	36296 KB	Output is correct
28	Correct	63 ms	35176 KB	Output is correct
29	Correct	70 ms	36028 KB	Output is correct
30	Correct	60 ms	35148 KB	Output is correct
31	Correct	68 ms	37572 KB	Output is correct
32	Correct	57 ms	38480 KB	Output is correct
33	Correct	57 ms	38312 KB	Output is correct
34	Correct	60 ms	38560 KB	Output is correct
35	Correct	60 ms	38276 KB	Output is correct
36	Correct	69 ms	37696 KB	Output is correct
37	Correct	74 ms	38464 KB	Output is correct
38	Correct	69 ms	38460 KB	Output is correct
39	Correct	65 ms	38716 KB	Output is correct
40	Correct	86 ms	38604 KB	Output is correct
41	Correct	59 ms	35224 KB	Output is correct
42	Correct	72 ms	36308 KB	Output is correct
43	Correct	74 ms	36384 KB	Output is correct
44	Correct	60 ms	35184 KB	Output is correct
45	Correct	102 ms	36260 KB	Output is correct
46	Correct	56 ms	35148 KB	Output is correct
47	Correct	69 ms	36060 KB	Output is correct
48	Correct	58 ms	35404 KB	Output is correct
49	Correct	66 ms	36016 KB	Output is correct
50	Correct	59 ms	35276 KB	Output is correct
51	Correct	77 ms	37244 KB	Output is correct
52	Correct	96 ms	38072 KB	Output is correct
53	Correct	96 ms	37300 KB	Output is correct
54	Correct	98 ms	38032 KB	Output is correct
55	Correct	80 ms	37268 KB	Output is correct

Subtask #10
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	31572 KB	Output is correct
2	Correct	17 ms	31572 KB	Output is correct
3	Correct	20 ms	31584 KB	Output is correct
4	Correct	17 ms	31564 KB	Output is correct
5	Correct	17 ms	31556 KB	Output is correct
6	Correct	18 ms	31652 KB	Output is correct
7	Correct	20 ms	31632 KB	Output is correct
8	Correct	20 ms	31612 KB	Output is correct
9	Correct	19 ms	31548 KB	Output is correct
10	Correct	20 ms	31572 KB	Output is correct
11	Correct	18 ms	31548 KB	Output is correct
12	Correct	19 ms	31628 KB	Output is correct
13	Correct	17 ms	31636 KB	Output is correct
14	Correct	18 ms	31572 KB	Output is correct
15	Correct	20 ms	31532 KB	Output is correct
16	Correct	18 ms	31644 KB	Output is correct
17	Correct	21 ms	31644 KB	Output is correct
18	Correct	17 ms	31568 KB	Output is correct
19	Correct	18 ms	31572 KB	Output is correct
20	Correct	18 ms	31572 KB	Output is correct
21	Correct	19 ms	31704 KB	Output is correct
22	Correct	19 ms	31700 KB	Output is correct
23	Correct	21 ms	31608 KB	Output is correct
24	Correct	20 ms	31592 KB	Output is correct
25	Correct	19 ms	31640 KB	Output is correct
26	Correct	58 ms	35272 KB	Output is correct
27	Correct	72 ms	36296 KB	Output is correct
28	Correct	63 ms	35176 KB	Output is correct
29	Correct	70 ms	36028 KB	Output is correct
30	Correct	60 ms	35148 KB	Output is correct
31	Correct	68 ms	37572 KB	Output is correct
32	Correct	57 ms	38480 KB	Output is correct
33	Correct	57 ms	38312 KB	Output is correct
34	Correct	60 ms	38560 KB	Output is correct
35	Correct	60 ms	38276 KB	Output is correct
36	Correct	69 ms	37696 KB	Output is correct
37	Correct	74 ms	38464 KB	Output is correct
38	Correct	69 ms	38460 KB	Output is correct
39	Correct	65 ms	38716 KB	Output is correct
40	Correct	86 ms	38604 KB	Output is correct
41	Correct	59 ms	35224 KB	Output is correct
42	Correct	72 ms	36308 KB	Output is correct
43	Correct	74 ms	36384 KB	Output is correct
44	Correct	60 ms	35184 KB	Output is correct
45	Correct	102 ms	36260 KB	Output is correct
46	Correct	56 ms	35148 KB	Output is correct
47	Correct	69 ms	36060 KB	Output is correct
48	Correct	58 ms	35404 KB	Output is correct
49	Correct	66 ms	36016 KB	Output is correct
50	Correct	59 ms	35276 KB	Output is correct
51	Correct	77 ms	37244 KB	Output is correct
52	Correct	96 ms	38072 KB	Output is correct
53	Correct	96 ms	37300 KB	Output is correct
54	Correct	98 ms	38032 KB	Output is correct
55	Correct	80 ms	37268 KB	Output is correct
56	Correct	947 ms	86356 KB	Output is correct
57	Correct	952 ms	87140 KB	Output is correct
58	Correct	844 ms	84020 KB	Output is correct
59	Correct	982 ms	85604 KB	Output is correct
60	Correct	991 ms	87956 KB	Output is correct

답안 #793899

Compilation message