oj.uz

답안 #320902

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
320902 2020-11-10T07:55:58 Z egas Pilot (NOI19_pilot) C++14
89 / 100
 1000 ms 54372 KB 
#include <bits/stdc++.h>

using namespace std;

template < typename third >

class SegmentTree {

private:

    third *Stree;

    third *Snum;

    long long n;

    third NullValue = 0;

    third combine(third a, third b) {

        return max(a,b);

    }

    void build(long long idx, long long s, long long e) {

        if (s > e)

            return;

        if (s == e) {

            Stree[idx] = Snum[s];

            return ;

        }

        long long m = ( s + e ) / 2;

        build( 2 * idx, s, m);

        build( 2 * idx + 1, m + 1, e);

        Stree[idx] = combine(Stree[2 * idx], Stree[2 * idx + 1] );

        return;

    }

    third queryUtil(long long idx, long long s, long long e, long long l, long long r) {

        if (l > e || r < s)

            return NullValue;

        if (s >= l && e <= r) {

            return Stree[idx];

        }

        long long m = ( s + e ) / 2;

        third left = queryUtil(2 * idx, s, m, l, r);

        third right = queryUtil(2 * idx + 1, m + 1, e, l, r);

        return combine(left, right );

    }

public:

    SegmentTree(vector<third> a) {

        this->n = a.size();

        Stree = new third[4 * n + 5];

        Snum = new third[n];

        for (long long i = 0; i < n; i++) {

            Snum[i] = a[i];

        }

        build(1, 0, n - 1);

    }

    third query(long long l, long long r) {

        return queryUtil(1, 0, n - 1, l - 1, r - 1);

    }

};

int32_t main() {

    ios_base::sync_with_stdio(false);

    cin.tie(0);

    long long n;

    cin >> n;

    long long m;

    cin >> m;

    vector<long long> a(n);

    for(long long i = 0 ; i < n ; i++) {

        cin >> a[i];

    }

    vector<long long> b(m);

    for(long long i = 0 ; i < m ; i++) {

        cin >> b[i];

    }

    vector<long long> diff(1000005,0);

    SegmentTree<long long> ST(a);

    long long *last=new long long[1000005];

    for(long long i = 0 ; i < a.size() ; i++) {

        last[a[i]]=-1;

    }

    for(long long i=0; i<n; i++) {

        long long ryt=0;

        long long l=i;

        long long r=a.size()-1;

        while(l<=r) {

            if(l==r) {

                if(ST.query(i+1,l+1)<=a[i]) {

                    ryt=max(ryt,l);

                }

                break;

            }

            long long m=(l+r)/2;

            if(ST.query(i+1,m+1)>a[i]) {

                r=m-1;

            } else {

                l=m+1;

                ryt=max(ryt,m);

            }

        }

        ryt=ryt-i+1;

        ryt--;

        long long left=1e9;

        l=last[a[i]]+1;

        r=i;

        while(l<=r) {

            if(l==r) {

                if(ST.query(l+1,i+1)<=a[i]) {

                    left=min(left,l);

                }

                break;

            }

            long long m=(l+r)/2;

            if(ST.query(m+1,i+1)>a[i]) {

                l=m+1;

            } else {

                r=m-1;

                left=min(left,m);

            }

        }

        left=i-left;

        last[a[i]]=i;

        diff[a[i]]+=((left+1)*(ryt+1));

    }

    for(long long i=1; i<diff.size(); i++) {

        diff[i]+=diff[i-1];

    }

    for(long long i = 0 ; i < b.size() ; i++) {

        cout << diff[b[i]] << '\n';

    }

    return 0;

}

Compilation message

pilot.cpp: In function 'int32_t main()':
pilot.cpp:137:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for(long long i = 0 ; i < a.size() ; i++) {
      |                           ~~^~~~~~~~~~
pilot.cpp:229:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  229 |     for(long long i=1; i<diff.size(); i++) {
      |                        ~^~~~~~~~~~~~
pilot.cpp:235:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  235 |     for(long long i = 0 ; i < b.size() ; i++) {
      |                           ~~^~~~~~~~~~

Subtask #1
3.0 / 3.0

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

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 8172 KB Output is correct
2 Correct 8 ms 8172 KB Output is correct
3 Correct 8 ms 8172 KB Output is correct
4 Correct 8 ms 8172 KB Output is correct
5 Correct 8 ms 8172 KB Output is correct
6 Correct 8 ms 8172 KB Output is correct
7 Correct 8 ms 8300 KB Output is correct
8 Correct 8 ms 8172 KB Output is correct
9 Correct 8 ms 8172 KB Output is correct
10 Correct 8 ms 8172 KB Output is correct
11 Correct 8 ms 8172 KB Output is correct
12 Correct 8 ms 8300 KB Output is correct
13 Correct 8 ms 8172 KB Output is correct
14 Correct 8 ms 8300 KB Output is correct
15 Correct 9 ms 8172 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 8172 KB Output is correct
2 Correct 8 ms 8172 KB Output is correct
3 Correct 8 ms 8172 KB Output is correct
4 Correct 8 ms 8172 KB Output is correct
5 Correct 8 ms 8172 KB Output is correct
6 Correct 8 ms 8172 KB Output is correct
7 Correct 8 ms 8300 KB Output is correct
8 Correct 8 ms 8172 KB Output is correct
9 Correct 8 ms 8172 KB Output is correct
10 Correct 8 ms 8172 KB Output is correct
11 Correct 8 ms 8172 KB Output is correct
12 Correct 8 ms 8300 KB Output is correct
13 Correct 8 ms 8172 KB Output is correct
14 Correct 8 ms 8300 KB Output is correct
15 Correct 9 ms 8172 KB Output is correct
16 Correct 8 ms 8172 KB Output is correct
17 Correct 9 ms 8940 KB Output is correct
18 Correct 8 ms 8172 KB Output is correct
19 Correct 9 ms 8940 KB Output is correct
20 Correct 8 ms 8172 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 8172 KB Output is correct
2 Correct 8 ms 8172 KB Output is correct
3 Correct 8 ms 8172 KB Output is correct
4 Correct 8 ms 8172 KB Output is correct
5 Correct 8 ms 8172 KB Output is correct
6 Correct 8 ms 8172 KB Output is correct
7 Correct 8 ms 8300 KB Output is correct
8 Correct 8 ms 8172 KB Output is correct
9 Correct 8 ms 8172 KB Output is correct
10 Correct 8 ms 8172 KB Output is correct
11 Correct 8 ms 8172 KB Output is correct
12 Correct 8 ms 8300 KB Output is correct
13 Correct 8 ms 8172 KB Output is correct
14 Correct 8 ms 8300 KB Output is correct
15 Correct 9 ms 8172 KB Output is correct
16 Correct 8 ms 8172 KB Output is correct
17 Correct 9 ms 8940 KB Output is correct
18 Correct 8 ms 8172 KB Output is correct
19 Correct 9 ms 8940 KB Output is correct
20 Correct 8 ms 8172 KB Output is correct
21 Correct 10 ms 8300 KB Output is correct
22 Correct 12 ms 11372 KB Output is correct
23 Correct 10 ms 8300 KB Output is correct
24 Correct 12 ms 11372 KB Output is correct
25 Correct 10 ms 8172 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 548 ms 12656 KB Output is correct
2 Correct 564 ms 19564 KB Output is correct
3 Correct 533 ms 12500 KB Output is correct
4 Correct 512 ms 19500 KB Output is correct
5 Correct 523 ms 12560 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 530 ms 14216 KB Output is correct
2 Correct 518 ms 14380 KB Output is correct
3 Correct 508 ms 14112 KB Output is correct
4 Correct 537 ms 14324 KB Output is correct
5 Correct 513 ms 14236 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 531 ms 21240 KB Output is correct
2 Correct 554 ms 21328 KB Output is correct
3 Correct 520 ms 21432 KB Output is correct
4 Correct 565 ms 21336 KB Output is correct
5 Correct 530 ms 21384 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 8172 KB Output is correct
2 Correct 8 ms 8172 KB Output is correct
3 Correct 8 ms 8172 KB Output is correct
4 Correct 8 ms 8172 KB Output is correct
5 Correct 8 ms 8172 KB Output is correct
6 Correct 8 ms 8172 KB Output is correct
7 Correct 8 ms 8300 KB Output is correct
8 Correct 8 ms 8172 KB Output is correct
9 Correct 8 ms 8172 KB Output is correct
10 Correct 8 ms 8172 KB Output is correct
11 Correct 548 ms 12656 KB Output is correct
12 Correct 564 ms 19564 KB Output is correct
13 Correct 533 ms 12500 KB Output is correct
14 Correct 512 ms 19500 KB Output is correct
15 Correct 523 ms 12560 KB Output is correct
16 Correct 524 ms 12560 KB Output is correct
17 Correct 565 ms 19684 KB Output is correct
18 Correct 575 ms 19676 KB Output is correct
19 Correct 513 ms 12448 KB Output is correct
20 Correct 554 ms 19700 KB Output is correct
21 Correct 509 ms 12440 KB Output is correct
22 Correct 540 ms 19600 KB Output is correct
23 Correct 602 ms 12524 KB Output is correct
24 Correct 537 ms 19488 KB Output is correct
25 Correct 545 ms 12540 KB Output is correct

Subtask #9
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 8172 KB Output is correct
2 Correct 8 ms 8172 KB Output is correct
3 Correct 8 ms 8172 KB Output is correct
4 Correct 8 ms 8172 KB Output is correct
5 Correct 8 ms 8172 KB Output is correct
6 Correct 8 ms 8172 KB Output is correct
7 Correct 8 ms 8300 KB Output is correct
8 Correct 8 ms 8172 KB Output is correct
9 Correct 8 ms 8172 KB Output is correct
10 Correct 8 ms 8172 KB Output is correct
11 Correct 8 ms 8172 KB Output is correct
12 Correct 8 ms 8300 KB Output is correct
13 Correct 8 ms 8172 KB Output is correct
14 Correct 8 ms 8300 KB Output is correct
15 Correct 9 ms 8172 KB Output is correct
16 Correct 8 ms 8172 KB Output is correct
17 Correct 9 ms 8940 KB Output is correct
18 Correct 8 ms 8172 KB Output is correct
19 Correct 9 ms 8940 KB Output is correct
20 Correct 8 ms 8172 KB Output is correct
21 Correct 10 ms 8300 KB Output is correct
22 Correct 12 ms 11372 KB Output is correct
23 Correct 10 ms 8300 KB Output is correct
24 Correct 12 ms 11372 KB Output is correct
25 Correct 10 ms 8172 KB Output is correct
26 Correct 548 ms 12656 KB Output is correct
27 Correct 564 ms 19564 KB Output is correct
28 Correct 533 ms 12500 KB Output is correct
29 Correct 512 ms 19500 KB Output is correct
30 Correct 523 ms 12560 KB Output is correct
31 Correct 530 ms 14216 KB Output is correct
32 Correct 518 ms 14380 KB Output is correct
33 Correct 508 ms 14112 KB Output is correct
34 Correct 537 ms 14324 KB Output is correct
35 Correct 513 ms 14236 KB Output is correct
36 Correct 531 ms 21240 KB Output is correct
37 Correct 554 ms 21328 KB Output is correct
38 Correct 520 ms 21432 KB Output is correct
39 Correct 565 ms 21336 KB Output is correct
40 Correct 530 ms 21384 KB Output is correct
41 Correct 524 ms 12560 KB Output is correct
42 Correct 565 ms 19684 KB Output is correct
43 Correct 575 ms 19676 KB Output is correct
44 Correct 513 ms 12448 KB Output is correct
45 Correct 554 ms 19700 KB Output is correct
46 Correct 509 ms 12440 KB Output is correct
47 Correct 540 ms 19600 KB Output is correct
48 Correct 602 ms 12524 KB Output is correct
49 Correct 537 ms 19488 KB Output is correct
50 Correct 545 ms 12540 KB Output is correct
51 Correct 563 ms 14348 KB Output is correct
52 Correct 593 ms 21004 KB Output is correct
53 Correct 600 ms 14184 KB Output is correct
54 Correct 573 ms 20992 KB Output is correct
55 Correct 584 ms 14048 KB Output is correct

Subtask #10
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 8172 KB Output is correct
2 Correct 8 ms 8172 KB Output is correct
3 Correct 8 ms 8172 KB Output is correct
4 Correct 8 ms 8172 KB Output is correct
5 Correct 8 ms 8172 KB Output is correct
6 Correct 8 ms 8172 KB Output is correct
7 Correct 8 ms 8300 KB Output is correct
8 Correct 8 ms 8172 KB Output is correct
9 Correct 8 ms 8172 KB Output is correct
10 Correct 8 ms 8172 KB Output is correct
11 Correct 8 ms 8172 KB Output is correct
12 Correct 8 ms 8300 KB Output is correct
13 Correct 8 ms 8172 KB Output is correct
14 Correct 8 ms 8300 KB Output is correct
15 Correct 9 ms 8172 KB Output is correct
16 Correct 8 ms 8172 KB Output is correct
17 Correct 9 ms 8940 KB Output is correct
18 Correct 8 ms 8172 KB Output is correct
19 Correct 9 ms 8940 KB Output is correct
20 Correct 8 ms 8172 KB Output is correct
21 Correct 10 ms 8300 KB Output is correct
22 Correct 12 ms 11372 KB Output is correct
23 Correct 10 ms 8300 KB Output is correct
24 Correct 12 ms 11372 KB Output is correct
25 Correct 10 ms 8172 KB Output is correct
26 Correct 548 ms 12656 KB Output is correct
27 Correct 564 ms 19564 KB Output is correct
28 Correct 533 ms 12500 KB Output is correct
29 Correct 512 ms 19500 KB Output is correct
30 Correct 523 ms 12560 KB Output is correct
31 Correct 530 ms 14216 KB Output is correct
32 Correct 518 ms 14380 KB Output is correct
33 Correct 508 ms 14112 KB Output is correct
34 Correct 537 ms 14324 KB Output is correct
35 Correct 513 ms 14236 KB Output is correct
36 Correct 531 ms 21240 KB Output is correct
37 Correct 554 ms 21328 KB Output is correct
38 Correct 520 ms 21432 KB Output is correct
39 Correct 565 ms 21336 KB Output is correct
40 Correct 530 ms 21384 KB Output is correct
41 Correct 524 ms 12560 KB Output is correct
42 Correct 565 ms 19684 KB Output is correct
43 Correct 575 ms 19676 KB Output is correct
44 Correct 513 ms 12448 KB Output is correct
45 Correct 554 ms 19700 KB Output is correct
46 Correct 509 ms 12440 KB Output is correct
47 Correct 540 ms 19600 KB Output is correct
48 Correct 602 ms 12524 KB Output is correct
49 Correct 537 ms 19488 KB Output is correct
50 Correct 545 ms 12540 KB Output is correct
51 Correct 563 ms 14348 KB Output is correct
52 Correct 593 ms 21004 KB Output is correct
53 Correct 600 ms 14184 KB Output is correct
54 Correct 573 ms 20992 KB Output is correct
55 Correct 584 ms 14048 KB Output is correct
56 Execution timed out 1101 ms 54372 KB Time limit exceeded
57 Halted 0 ms 0 KB -