oj.uz

Submission #471830

# Submission time Handle Problem Language Result Execution time Memory
471830 2021-09-11T05:04:10 Z jazzup Pilot (NOI19_pilot) C++14
89 / 100
 1000 ms 104916 KB 
/*input
6 3
1 3 2 4 1 2
2 3 4
*/
//NOI-SG 2019
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>

using namespace std;

long long ans[1000007];
pair<int,int> a[1000007];
set<int> b;
vector<int> v[1000007];

int main(){
	long long n,q,y;
	set<int>::iterator it;
	int sc;
	scanf("%lld%lld",&n,&q);
	for(int i=0;i<n;i++){
		scanf("%d",&sc);
		v[sc].push_back(i+1);
	}

	int cnt=0;

	for(int i=1;i<=1000000;i++){
		for(int j=0;j<v[i].size();j++){
			a[cnt].first=i;
			a[cnt].second=v[i][j];
			cnt++;
		}
	}

	long long cur= (n*(n-1))/2 + n;

	int idx=n-1;
	b.insert(0);
	b.insert(n+1);

	for(int i=1000000;i>0;i--){
		while(i<a[idx].first){
			it=b.lower_bound(a[idx].second);
			long long r=*it;

			it--;
			long long l=*it;
			
			long long diff=r-l-1;
			cur-=((diff*(diff-1))/2 + diff);

			diff=r-a[idx].second-1;
			cur+=((diff*(diff-1))/2 + diff);

			diff=a[idx].second-l-1;
			cur+=((diff*(diff-1))/2 + diff);

			b.insert(a[idx].second);

			idx--;

			if(idx<0){
				break;
			}
		}
		if(idx<0)break;
		ans[i]=cur;
	}

	for(int i=0;i<q;i++){
		scanf("%lld",&y);
		printf("%lld\n",ans[y]);
	}
	return 0;

}

Compilation message

pilot.cpp: In function 'int main()':
pilot.cpp:32:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int j=0;j<v[i].size();j++){
      |               ~^~~~~~~~~~~~
pilot.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%lld%lld",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
pilot.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%d",&sc);
      |   ~~~~~^~~~~~~~~~
pilot.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   scanf("%lld",&y);
      |   ~~~~~^~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31556 KB Output is correct
2 Correct 19 ms 28544 KB Output is correct
3 Correct 21 ms 29660 KB Output is correct
4 Correct 22 ms 31560 KB Output is correct
5 Correct 19 ms 27468 KB Output is correct
6 Correct 21 ms 31576 KB Output is correct
7 Correct 18 ms 27852 KB Output is correct
8 Correct 21 ms 31580 KB Output is correct
9 Correct 18 ms 26572 KB Output is correct
10 Correct 21 ms 31564 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31556 KB Output is correct
2 Correct 19 ms 28544 KB Output is correct
3 Correct 21 ms 29660 KB Output is correct
4 Correct 22 ms 31560 KB Output is correct
5 Correct 19 ms 27468 KB Output is correct
6 Correct 21 ms 31576 KB Output is correct
7 Correct 18 ms 27852 KB Output is correct
8 Correct 21 ms 31580 KB Output is correct
9 Correct 18 ms 26572 KB Output is correct
10 Correct 21 ms 31564 KB Output is correct
11 Correct 21 ms 31516 KB Output is correct
12 Correct 21 ms 31456 KB Output is correct
13 Correct 22 ms 31604 KB Output is correct
14 Correct 21 ms 31068 KB Output is correct
15 Correct 21 ms 31564 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31556 KB Output is correct
2 Correct 19 ms 28544 KB Output is correct
3 Correct 21 ms 29660 KB Output is correct
4 Correct 22 ms 31560 KB Output is correct
5 Correct 19 ms 27468 KB Output is correct
6 Correct 21 ms 31576 KB Output is correct
7 Correct 18 ms 27852 KB Output is correct
8 Correct 21 ms 31580 KB Output is correct
9 Correct 18 ms 26572 KB Output is correct
10 Correct 21 ms 31564 KB Output is correct
11 Correct 21 ms 31516 KB Output is correct
12 Correct 21 ms 31456 KB Output is correct
13 Correct 22 ms 31604 KB Output is correct
14 Correct 21 ms 31068 KB Output is correct
15 Correct 21 ms 31564 KB Output is correct
16 Correct 21 ms 31516 KB Output is correct
17 Correct 24 ms 31584 KB Output is correct
18 Correct 22 ms 31592 KB Output is correct
19 Correct 22 ms 31556 KB Output is correct
20 Correct 21 ms 31548 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31556 KB Output is correct
2 Correct 19 ms 28544 KB Output is correct
3 Correct 21 ms 29660 KB Output is correct
4 Correct 22 ms 31560 KB Output is correct
5 Correct 19 ms 27468 KB Output is correct
6 Correct 21 ms 31576 KB Output is correct
7 Correct 18 ms 27852 KB Output is correct
8 Correct 21 ms 31580 KB Output is correct
9 Correct 18 ms 26572 KB Output is correct
10 Correct 21 ms 31564 KB Output is correct
11 Correct 21 ms 31516 KB Output is correct
12 Correct 21 ms 31456 KB Output is correct
13 Correct 22 ms 31604 KB Output is correct
14 Correct 21 ms 31068 KB Output is correct
15 Correct 21 ms 31564 KB Output is correct
16 Correct 21 ms 31516 KB Output is correct
17 Correct 24 ms 31584 KB Output is correct
18 Correct 22 ms 31592 KB Output is correct
19 Correct 22 ms 31556 KB Output is correct
20 Correct 21 ms 31548 KB Output is correct
21 Correct 22 ms 31652 KB Output is correct
22 Correct 21 ms 31564 KB Output is correct
23 Correct 22 ms 31688 KB Output is correct
24 Correct 24 ms 31592 KB Output is correct
25 Correct 24 ms 31668 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 39360 KB Output is correct
2 Correct 111 ms 40616 KB Output is correct
3 Correct 88 ms 39004 KB Output is correct
4 Correct 112 ms 39748 KB Output is correct
5 Correct 87 ms 38936 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 41688 KB Output is correct
2 Correct 107 ms 41828 KB Output is correct
3 Correct 104 ms 41432 KB Output is correct
4 Correct 101 ms 41940 KB Output is correct
5 Correct 99 ms 41416 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 41956 KB Output is correct
2 Correct 107 ms 41704 KB Output is correct
3 Correct 109 ms 41516 KB Output is correct
4 Correct 114 ms 42460 KB Output is correct
5 Correct 111 ms 41924 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31556 KB Output is correct
2 Correct 19 ms 28544 KB Output is correct
3 Correct 21 ms 29660 KB Output is correct
4 Correct 22 ms 31560 KB Output is correct
5 Correct 19 ms 27468 KB Output is correct
6 Correct 21 ms 31576 KB Output is correct
7 Correct 18 ms 27852 KB Output is correct
8 Correct 21 ms 31580 KB Output is correct
9 Correct 18 ms 26572 KB Output is correct
10 Correct 21 ms 31564 KB Output is correct
11 Correct 93 ms 39360 KB Output is correct
12 Correct 111 ms 40616 KB Output is correct
13 Correct 88 ms 39004 KB Output is correct
14 Correct 112 ms 39748 KB Output is correct
15 Correct 87 ms 38936 KB Output is correct
16 Correct 83 ms 38952 KB Output is correct
17 Correct 108 ms 40432 KB Output is correct
18 Correct 112 ms 40580 KB Output is correct
19 Correct 89 ms 38852 KB Output is correct
20 Correct 108 ms 40372 KB Output is correct
21 Correct 86 ms 38904 KB Output is correct
22 Correct 104 ms 40004 KB Output is correct
23 Correct 101 ms 39652 KB Output is correct
24 Correct 105 ms 39932 KB Output is correct
25 Correct 89 ms 39236 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31556 KB Output is correct
2 Correct 19 ms 28544 KB Output is correct
3 Correct 21 ms 29660 KB Output is correct
4 Correct 22 ms 31560 KB Output is correct
5 Correct 19 ms 27468 KB Output is correct
6 Correct 21 ms 31576 KB Output is correct
7 Correct 18 ms 27852 KB Output is correct
8 Correct 21 ms 31580 KB Output is correct
9 Correct 18 ms 26572 KB Output is correct
10 Correct 21 ms 31564 KB Output is correct
11 Correct 21 ms 31516 KB Output is correct
12 Correct 21 ms 31456 KB Output is correct
13 Correct 22 ms 31604 KB Output is correct
14 Correct 21 ms 31068 KB Output is correct
15 Correct 21 ms 31564 KB Output is correct
16 Correct 21 ms 31516 KB Output is correct
17 Correct 24 ms 31584 KB Output is correct
18 Correct 22 ms 31592 KB Output is correct
19 Correct 22 ms 31556 KB Output is correct
20 Correct 21 ms 31548 KB Output is correct
21 Correct 22 ms 31652 KB Output is correct
22 Correct 21 ms 31564 KB Output is correct
23 Correct 22 ms 31688 KB Output is correct
24 Correct 24 ms 31592 KB Output is correct
25 Correct 24 ms 31668 KB Output is correct
26 Correct 93 ms 39360 KB Output is correct
27 Correct 111 ms 40616 KB Output is correct
28 Correct 88 ms 39004 KB Output is correct
29 Correct 112 ms 39748 KB Output is correct
30 Correct 87 ms 38936 KB Output is correct
31 Correct 102 ms 41688 KB Output is correct
32 Correct 107 ms 41828 KB Output is correct
33 Correct 104 ms 41432 KB Output is correct
34 Correct 101 ms 41940 KB Output is correct
35 Correct 99 ms 41416 KB Output is correct
36 Correct 114 ms 41956 KB Output is correct
37 Correct 107 ms 41704 KB Output is correct
38 Correct 109 ms 41516 KB Output is correct
39 Correct 114 ms 42460 KB Output is correct
40 Correct 111 ms 41924 KB Output is correct
41 Correct 83 ms 38952 KB Output is correct
42 Correct 108 ms 40432 KB Output is correct
43 Correct 112 ms 40580 KB Output is correct
44 Correct 89 ms 38852 KB Output is correct
45 Correct 108 ms 40372 KB Output is correct
46 Correct 86 ms 38904 KB Output is correct
47 Correct 104 ms 40004 KB Output is correct
48 Correct 101 ms 39652 KB Output is correct
49 Correct 105 ms 39932 KB Output is correct
50 Correct 89 ms 39236 KB Output is correct
51 Correct 124 ms 40700 KB Output is correct
52 Correct 143 ms 41356 KB Output is correct
53 Correct 121 ms 40752 KB Output is correct
54 Correct 137 ms 41416 KB Output is correct
55 Correct 127 ms 40808 KB Output is correct

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31556 KB Output is correct
2 Correct 19 ms 28544 KB Output is correct
3 Correct 21 ms 29660 KB Output is correct
4 Correct 22 ms 31560 KB Output is correct
5 Correct 19 ms 27468 KB Output is correct
6 Correct 21 ms 31576 KB Output is correct
7 Correct 18 ms 27852 KB Output is correct
8 Correct 21 ms 31580 KB Output is correct
9 Correct 18 ms 26572 KB Output is correct
10 Correct 21 ms 31564 KB Output is correct
11 Correct 21 ms 31516 KB Output is correct
12 Correct 21 ms 31456 KB Output is correct
13 Correct 22 ms 31604 KB Output is correct
14 Correct 21 ms 31068 KB Output is correct
15 Correct 21 ms 31564 KB Output is correct
16 Correct 21 ms 31516 KB Output is correct
17 Correct 24 ms 31584 KB Output is correct
18 Correct 22 ms 31592 KB Output is correct
19 Correct 22 ms 31556 KB Output is correct
20 Correct 21 ms 31548 KB Output is correct
21 Correct 22 ms 31652 KB Output is correct
22 Correct 21 ms 31564 KB Output is correct
23 Correct 22 ms 31688 KB Output is correct
24 Correct 24 ms 31592 KB Output is correct
25 Correct 24 ms 31668 KB Output is correct
26 Correct 93 ms 39360 KB Output is correct
27 Correct 111 ms 40616 KB Output is correct
28 Correct 88 ms 39004 KB Output is correct
29 Correct 112 ms 39748 KB Output is correct
30 Correct 87 ms 38936 KB Output is correct
31 Correct 102 ms 41688 KB Output is correct
32 Correct 107 ms 41828 KB Output is correct
33 Correct 104 ms 41432 KB Output is correct
34 Correct 101 ms 41940 KB Output is correct
35 Correct 99 ms 41416 KB Output is correct
36 Correct 114 ms 41956 KB Output is correct
37 Correct 107 ms 41704 KB Output is correct
38 Correct 109 ms 41516 KB Output is correct
39 Correct 114 ms 42460 KB Output is correct
40 Correct 111 ms 41924 KB Output is correct
41 Correct 83 ms 38952 KB Output is correct
42 Correct 108 ms 40432 KB Output is correct
43 Correct 112 ms 40580 KB Output is correct
44 Correct 89 ms 38852 KB Output is correct
45 Correct 108 ms 40372 KB Output is correct
46 Correct 86 ms 38904 KB Output is correct
47 Correct 104 ms 40004 KB Output is correct
48 Correct 101 ms 39652 KB Output is correct
49 Correct 105 ms 39932 KB Output is correct
50 Correct 89 ms 39236 KB Output is correct
51 Correct 124 ms 40700 KB Output is correct
52 Correct 143 ms 41356 KB Output is correct
53 Correct 121 ms 40752 KB Output is correct
54 Correct 137 ms 41416 KB Output is correct
55 Correct 127 ms 40808 KB Output is correct
56 Execution timed out 1092 ms 104916 KB Time limit exceeded
57 Halted 0 ms 0 KB -