oj.uz

Submission #471529

# Submission time Handle Problem Language Result Execution time Memory
471529 2021-09-09T16:30:51 Z jazzup Pilot (NOI19_pilot) C++14
89 / 100
 1000 ms 75304 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<long long,long long> a[1000007];
set<long long> b;

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

	sort(a,a+n,greater<pair<long long,long long> >());

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

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

	for(long long 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==n){
				break;
			}
		}
		if(idx==n)break;
		ans[i]=cur;
	}

	for(long long 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:21:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  scanf("%lld%lld",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
pilot.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("%lld",&a[i].first);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
pilot.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   scanf("%lld",&y);
      |   ~~~~~^~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8012 KB Output is correct
2 Correct 4 ms 5200 KB Output is correct
3 Correct 4 ms 6220 KB Output is correct
4 Correct 5 ms 8012 KB Output is correct
5 Correct 3 ms 4044 KB Output is correct
6 Correct 5 ms 8012 KB Output is correct
7 Correct 3 ms 4432 KB Output is correct
8 Correct 6 ms 8128 KB Output is correct
9 Correct 2 ms 3160 KB Output is correct
10 Correct 5 ms 8024 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8012 KB Output is correct
2 Correct 4 ms 5200 KB Output is correct
3 Correct 4 ms 6220 KB Output is correct
4 Correct 5 ms 8012 KB Output is correct
5 Correct 3 ms 4044 KB Output is correct
6 Correct 5 ms 8012 KB Output is correct
7 Correct 3 ms 4432 KB Output is correct
8 Correct 6 ms 8128 KB Output is correct
9 Correct 2 ms 3160 KB Output is correct
10 Correct 5 ms 8024 KB Output is correct
11 Correct 5 ms 8024 KB Output is correct
12 Correct 6 ms 8024 KB Output is correct
13 Correct 5 ms 8024 KB Output is correct
14 Correct 5 ms 7640 KB Output is correct
15 Correct 5 ms 8024 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8012 KB Output is correct
2 Correct 4 ms 5200 KB Output is correct
3 Correct 4 ms 6220 KB Output is correct
4 Correct 5 ms 8012 KB Output is correct
5 Correct 3 ms 4044 KB Output is correct
6 Correct 5 ms 8012 KB Output is correct
7 Correct 3 ms 4432 KB Output is correct
8 Correct 6 ms 8128 KB Output is correct
9 Correct 2 ms 3160 KB Output is correct
10 Correct 5 ms 8024 KB Output is correct
11 Correct 5 ms 8024 KB Output is correct
12 Correct 6 ms 8024 KB Output is correct
13 Correct 5 ms 8024 KB Output is correct
14 Correct 5 ms 7640 KB Output is correct
15 Correct 5 ms 8024 KB Output is correct
16 Correct 5 ms 8024 KB Output is correct
17 Correct 5 ms 8112 KB Output is correct
18 Correct 5 ms 8016 KB Output is correct
19 Correct 6 ms 8020 KB Output is correct
20 Correct 6 ms 8020 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8012 KB Output is correct
2 Correct 4 ms 5200 KB Output is correct
3 Correct 4 ms 6220 KB Output is correct
4 Correct 5 ms 8012 KB Output is correct
5 Correct 3 ms 4044 KB Output is correct
6 Correct 5 ms 8012 KB Output is correct
7 Correct 3 ms 4432 KB Output is correct
8 Correct 6 ms 8128 KB Output is correct
9 Correct 2 ms 3160 KB Output is correct
10 Correct 5 ms 8024 KB Output is correct
11 Correct 5 ms 8024 KB Output is correct
12 Correct 6 ms 8024 KB Output is correct
13 Correct 5 ms 8024 KB Output is correct
14 Correct 5 ms 7640 KB Output is correct
15 Correct 5 ms 8024 KB Output is correct
16 Correct 5 ms 8024 KB Output is correct
17 Correct 5 ms 8112 KB Output is correct
18 Correct 5 ms 8016 KB Output is correct
19 Correct 6 ms 8020 KB Output is correct
20 Correct 6 ms 8020 KB Output is correct
21 Correct 6 ms 8152 KB Output is correct
22 Correct 6 ms 8092 KB Output is correct
23 Correct 6 ms 8144 KB Output is correct
24 Correct 6 ms 8148 KB Output is correct
25 Correct 6 ms 8148 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 14344 KB Output is correct
2 Correct 65 ms 14820 KB Output is correct
3 Correct 64 ms 14396 KB Output is correct
4 Correct 60 ms 14336 KB Output is correct
5 Correct 61 ms 14412 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 15124 KB Output is correct
2 Correct 83 ms 16056 KB Output is correct
3 Correct 79 ms 15812 KB Output is correct
4 Correct 81 ms 16204 KB Output is correct
5 Correct 79 ms 15900 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 15220 KB Output is correct
2 Correct 91 ms 16076 KB Output is correct
3 Correct 84 ms 15972 KB Output is correct
4 Correct 85 ms 16452 KB Output is correct
5 Correct 84 ms 16308 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8012 KB Output is correct
2 Correct 4 ms 5200 KB Output is correct
3 Correct 4 ms 6220 KB Output is correct
4 Correct 5 ms 8012 KB Output is correct
5 Correct 3 ms 4044 KB Output is correct
6 Correct 5 ms 8012 KB Output is correct
7 Correct 3 ms 4432 KB Output is correct
8 Correct 6 ms 8128 KB Output is correct
9 Correct 2 ms 3160 KB Output is correct
10 Correct 5 ms 8024 KB Output is correct
11 Correct 63 ms 14344 KB Output is correct
12 Correct 65 ms 14820 KB Output is correct
13 Correct 64 ms 14396 KB Output is correct
14 Correct 60 ms 14336 KB Output is correct
15 Correct 61 ms 14412 KB Output is correct
16 Correct 61 ms 14400 KB Output is correct
17 Correct 70 ms 14820 KB Output is correct
18 Correct 66 ms 14920 KB Output is correct
19 Correct 61 ms 14272 KB Output is correct
20 Correct 64 ms 14712 KB Output is correct
21 Correct 66 ms 14352 KB Output is correct
22 Correct 62 ms 14512 KB Output is correct
23 Correct 66 ms 14788 KB Output is correct
24 Correct 63 ms 14324 KB Output is correct
25 Correct 65 ms 14564 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8012 KB Output is correct
2 Correct 4 ms 5200 KB Output is correct
3 Correct 4 ms 6220 KB Output is correct
4 Correct 5 ms 8012 KB Output is correct
5 Correct 3 ms 4044 KB Output is correct
6 Correct 5 ms 8012 KB Output is correct
7 Correct 3 ms 4432 KB Output is correct
8 Correct 6 ms 8128 KB Output is correct
9 Correct 2 ms 3160 KB Output is correct
10 Correct 5 ms 8024 KB Output is correct
11 Correct 5 ms 8024 KB Output is correct
12 Correct 6 ms 8024 KB Output is correct
13 Correct 5 ms 8024 KB Output is correct
14 Correct 5 ms 7640 KB Output is correct
15 Correct 5 ms 8024 KB Output is correct
16 Correct 5 ms 8024 KB Output is correct
17 Correct 5 ms 8112 KB Output is correct
18 Correct 5 ms 8016 KB Output is correct
19 Correct 6 ms 8020 KB Output is correct
20 Correct 6 ms 8020 KB Output is correct
21 Correct 6 ms 8152 KB Output is correct
22 Correct 6 ms 8092 KB Output is correct
23 Correct 6 ms 8144 KB Output is correct
24 Correct 6 ms 8148 KB Output is correct
25 Correct 6 ms 8148 KB Output is correct
26 Correct 63 ms 14344 KB Output is correct
27 Correct 65 ms 14820 KB Output is correct
28 Correct 64 ms 14396 KB Output is correct
29 Correct 60 ms 14336 KB Output is correct
30 Correct 61 ms 14412 KB Output is correct
31 Correct 79 ms 15124 KB Output is correct
32 Correct 83 ms 16056 KB Output is correct
33 Correct 79 ms 15812 KB Output is correct
34 Correct 81 ms 16204 KB Output is correct
35 Correct 79 ms 15900 KB Output is correct
36 Correct 82 ms 15220 KB Output is correct
37 Correct 91 ms 16076 KB Output is correct
38 Correct 84 ms 15972 KB Output is correct
39 Correct 85 ms 16452 KB Output is correct
40 Correct 84 ms 16308 KB Output is correct
41 Correct 61 ms 14400 KB Output is correct
42 Correct 70 ms 14820 KB Output is correct
43 Correct 66 ms 14920 KB Output is correct
44 Correct 61 ms 14272 KB Output is correct
45 Correct 64 ms 14712 KB Output is correct
46 Correct 66 ms 14352 KB Output is correct
47 Correct 62 ms 14512 KB Output is correct
48 Correct 66 ms 14788 KB Output is correct
49 Correct 63 ms 14324 KB Output is correct
50 Correct 65 ms 14564 KB Output is correct
51 Correct 99 ms 16048 KB Output is correct
52 Correct 101 ms 16088 KB Output is correct
53 Correct 97 ms 16080 KB Output is correct
54 Correct 97 ms 15856 KB Output is correct
55 Correct 97 ms 16164 KB Output is correct

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8012 KB Output is correct
2 Correct 4 ms 5200 KB Output is correct
3 Correct 4 ms 6220 KB Output is correct
4 Correct 5 ms 8012 KB Output is correct
5 Correct 3 ms 4044 KB Output is correct
6 Correct 5 ms 8012 KB Output is correct
7 Correct 3 ms 4432 KB Output is correct
8 Correct 6 ms 8128 KB Output is correct
9 Correct 2 ms 3160 KB Output is correct
10 Correct 5 ms 8024 KB Output is correct
11 Correct 5 ms 8024 KB Output is correct
12 Correct 6 ms 8024 KB Output is correct
13 Correct 5 ms 8024 KB Output is correct
14 Correct 5 ms 7640 KB Output is correct
15 Correct 5 ms 8024 KB Output is correct
16 Correct 5 ms 8024 KB Output is correct
17 Correct 5 ms 8112 KB Output is correct
18 Correct 5 ms 8016 KB Output is correct
19 Correct 6 ms 8020 KB Output is correct
20 Correct 6 ms 8020 KB Output is correct
21 Correct 6 ms 8152 KB Output is correct
22 Correct 6 ms 8092 KB Output is correct
23 Correct 6 ms 8144 KB Output is correct
24 Correct 6 ms 8148 KB Output is correct
25 Correct 6 ms 8148 KB Output is correct
26 Correct 63 ms 14344 KB Output is correct
27 Correct 65 ms 14820 KB Output is correct
28 Correct 64 ms 14396 KB Output is correct
29 Correct 60 ms 14336 KB Output is correct
30 Correct 61 ms 14412 KB Output is correct
31 Correct 79 ms 15124 KB Output is correct
32 Correct 83 ms 16056 KB Output is correct
33 Correct 79 ms 15812 KB Output is correct
34 Correct 81 ms 16204 KB Output is correct
35 Correct 79 ms 15900 KB Output is correct
36 Correct 82 ms 15220 KB Output is correct
37 Correct 91 ms 16076 KB Output is correct
38 Correct 84 ms 15972 KB Output is correct
39 Correct 85 ms 16452 KB Output is correct
40 Correct 84 ms 16308 KB Output is correct
41 Correct 61 ms 14400 KB Output is correct
42 Correct 70 ms 14820 KB Output is correct
43 Correct 66 ms 14920 KB Output is correct
44 Correct 61 ms 14272 KB Output is correct
45 Correct 64 ms 14712 KB Output is correct
46 Correct 66 ms 14352 KB Output is correct
47 Correct 62 ms 14512 KB Output is correct
48 Correct 66 ms 14788 KB Output is correct
49 Correct 63 ms 14324 KB Output is correct
50 Correct 65 ms 14564 KB Output is correct
51 Correct 99 ms 16048 KB Output is correct
52 Correct 101 ms 16088 KB Output is correct
53 Correct 97 ms 16080 KB Output is correct
54 Correct 97 ms 15856 KB Output is correct
55 Correct 97 ms 16164 KB Output is correct
56 Execution timed out 1084 ms 75304 KB Time limit exceeded
57 Halted 0 ms 0 KB -