oj.uz

Submission #20962

# Submission time Handle Problem Language Result Execution time Memory
20962 2017-03-23T05:54:05 Z kdh9949 Rope (JOI17_rope) C++14
100 / 100
 1816 ms 135280 KB 
#include <bits/stdc++.h>
using namespace std;

const int sz = 1048576;
struct Seg{
	int dat[2 * sz];
	void upd(int x, int v){
		x += sz - 1; dat[x] += v;
		for(x /= 2; x; x /= 2) dat[x] = max(dat[2 * x], dat[2 * x + 1]);
	}
	int get(){ return dat[1]; }
} S;

int n, m, a[1000010], b[1000010][2], c[1000010];
vector<int> d[1000010][2];

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d", a + i);
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 2; j++){
			int nx = i + 1 - (i + j) % 2 * 2;
			if(a[nx] && a[nx] != a[i]) d[a[i]][j].push_back(a[nx]);
		}
		S.upd(a[i], 1);
		c[a[i]]++;
	}
	for(int i = 1; i <= m; i++){
		S.upd(i, -c[i]);
		int ans = n;
		for(int j = 0; j < 2; j++){
			for(auto &k : d[i][j]) S.upd(k, -1);
			ans = min(ans, n - c[i] - S.get());
			for(auto &k : d[i][j]) S.upd(k, 1);
		}
		S.upd(i, c[i]);
		printf("%d\n", ans);
	}
}

Compilation message

rope.cpp: In function 'int main()':
rope.cpp:18:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
rope.cpp:19:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= n; i++) scanf("%d", a + i);
                                                ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 72712 KB Output is correct
2 Correct 16 ms 72712 KB Output is correct
3 Correct 16 ms 72712 KB Output is correct
4 Correct 9 ms 72712 KB Output is correct
5 Correct 6 ms 72712 KB Output is correct
6 Correct 6 ms 72712 KB Output is correct
7 Correct 9 ms 72712 KB Output is correct
8 Correct 9 ms 72712 KB Output is correct
9 Correct 6 ms 72712 KB Output is correct
10 Correct 9 ms 72712 KB Output is correct
11 Correct 9 ms 72712 KB Output is correct
12 Correct 9 ms 72712 KB Output is correct
13 Correct 19 ms 72712 KB Output is correct
14 Correct 6 ms 72712 KB Output is correct
15 Correct 3 ms 72712 KB Output is correct
16 Correct 9 ms 72712 KB Output is correct
17 Correct 13 ms 72712 KB Output is correct
18 Correct 9 ms 72712 KB Output is correct
19 Correct 6 ms 72712 KB Output is correct
20 Correct 16 ms 72712 KB Output is correct
21 Correct 13 ms 72712 KB Output is correct
22 Correct 9 ms 72712 KB Output is correct
23 Correct 13 ms 72712 KB Output is correct
24 Correct 13 ms 72712 KB Output is correct
25 Correct 16 ms 72712 KB Output is correct
26 Correct 6 ms 72712 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 72712 KB Output is correct
2 Correct 16 ms 72712 KB Output is correct
3 Correct 16 ms 72712 KB Output is correct
4 Correct 9 ms 72712 KB Output is correct
5 Correct 6 ms 72712 KB Output is correct
6 Correct 6 ms 72712 KB Output is correct
7 Correct 9 ms 72712 KB Output is correct
8 Correct 9 ms 72712 KB Output is correct
9 Correct 6 ms 72712 KB Output is correct
10 Correct 9 ms 72712 KB Output is correct
11 Correct 9 ms 72712 KB Output is correct
12 Correct 9 ms 72712 KB Output is correct
13 Correct 19 ms 72712 KB Output is correct
14 Correct 6 ms 72712 KB Output is correct
15 Correct 3 ms 72712 KB Output is correct
16 Correct 9 ms 72712 KB Output is correct
17 Correct 13 ms 72712 KB Output is correct
18 Correct 9 ms 72712 KB Output is correct
19 Correct 6 ms 72712 KB Output is correct
20 Correct 16 ms 72712 KB Output is correct
21 Correct 13 ms 72712 KB Output is correct
22 Correct 9 ms 72712 KB Output is correct
23 Correct 13 ms 72712 KB Output is correct
24 Correct 13 ms 72712 KB Output is correct
25 Correct 16 ms 72712 KB Output is correct
26 Correct 6 ms 72712 KB Output is correct
27 Correct 53 ms 74176 KB Output is correct
28 Correct 46 ms 73888 KB Output is correct
29 Correct 49 ms 74072 KB Output is correct
30 Correct 56 ms 73492 KB Output is correct
31 Correct 53 ms 74208 KB Output is correct
32 Correct 46 ms 73884 KB Output is correct
33 Correct 56 ms 74076 KB Output is correct
34 Correct 53 ms 73492 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 72712 KB Output is correct
2 Correct 16 ms 72712 KB Output is correct
3 Correct 16 ms 72712 KB Output is correct
4 Correct 9 ms 72712 KB Output is correct
5 Correct 6 ms 72712 KB Output is correct
6 Correct 6 ms 72712 KB Output is correct
7 Correct 9 ms 72712 KB Output is correct
8 Correct 9 ms 72712 KB Output is correct
9 Correct 6 ms 72712 KB Output is correct
10 Correct 9 ms 72712 KB Output is correct
11 Correct 9 ms 72712 KB Output is correct
12 Correct 9 ms 72712 KB Output is correct
13 Correct 19 ms 72712 KB Output is correct
14 Correct 6 ms 72712 KB Output is correct
15 Correct 3 ms 72712 KB Output is correct
16 Correct 9 ms 72712 KB Output is correct
17 Correct 13 ms 72712 KB Output is correct
18 Correct 9 ms 72712 KB Output is correct
19 Correct 6 ms 72712 KB Output is correct
20 Correct 16 ms 72712 KB Output is correct
21 Correct 13 ms 72712 KB Output is correct
22 Correct 9 ms 72712 KB Output is correct
23 Correct 13 ms 72712 KB Output is correct
24 Correct 13 ms 72712 KB Output is correct
25 Correct 16 ms 72712 KB Output is correct
26 Correct 6 ms 72712 KB Output is correct
27 Correct 53 ms 74176 KB Output is correct
28 Correct 46 ms 73888 KB Output is correct
29 Correct 49 ms 74072 KB Output is correct
30 Correct 56 ms 73492 KB Output is correct
31 Correct 53 ms 74208 KB Output is correct
32 Correct 46 ms 73884 KB Output is correct
33 Correct 56 ms 74076 KB Output is correct
34 Correct 53 ms 73492 KB Output is correct
35 Correct 53 ms 73768 KB Output is correct
36 Correct 56 ms 73768 KB Output is correct
37 Correct 46 ms 73768 KB Output is correct
38 Correct 59 ms 73768 KB Output is correct
39 Correct 56 ms 73768 KB Output is correct
40 Correct 59 ms 74032 KB Output is correct
41 Correct 53 ms 74032 KB Output is correct
42 Correct 59 ms 73900 KB Output is correct
43 Correct 66 ms 74032 KB Output is correct
44 Correct 63 ms 74032 KB Output is correct
45 Correct 63 ms 74032 KB Output is correct
46 Correct 56 ms 73900 KB Output is correct
47 Correct 46 ms 74032 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 72712 KB Output is correct
2 Correct 16 ms 72712 KB Output is correct
3 Correct 16 ms 72712 KB Output is correct
4 Correct 9 ms 72712 KB Output is correct
5 Correct 6 ms 72712 KB Output is correct
6 Correct 6 ms 72712 KB Output is correct
7 Correct 9 ms 72712 KB Output is correct
8 Correct 9 ms 72712 KB Output is correct
9 Correct 6 ms 72712 KB Output is correct
10 Correct 9 ms 72712 KB Output is correct
11 Correct 9 ms 72712 KB Output is correct
12 Correct 9 ms 72712 KB Output is correct
13 Correct 19 ms 72712 KB Output is correct
14 Correct 6 ms 72712 KB Output is correct
15 Correct 3 ms 72712 KB Output is correct
16 Correct 9 ms 72712 KB Output is correct
17 Correct 13 ms 72712 KB Output is correct
18 Correct 9 ms 72712 KB Output is correct
19 Correct 6 ms 72712 KB Output is correct
20 Correct 16 ms 72712 KB Output is correct
21 Correct 13 ms 72712 KB Output is correct
22 Correct 9 ms 72712 KB Output is correct
23 Correct 13 ms 72712 KB Output is correct
24 Correct 13 ms 72712 KB Output is correct
25 Correct 16 ms 72712 KB Output is correct
26 Correct 6 ms 72712 KB Output is correct
27 Correct 53 ms 74176 KB Output is correct
28 Correct 46 ms 73888 KB Output is correct
29 Correct 49 ms 74072 KB Output is correct
30 Correct 56 ms 73492 KB Output is correct
31 Correct 53 ms 74208 KB Output is correct
32 Correct 46 ms 73884 KB Output is correct
33 Correct 56 ms 74076 KB Output is correct
34 Correct 53 ms 73492 KB Output is correct
35 Correct 53 ms 73768 KB Output is correct
36 Correct 56 ms 73768 KB Output is correct
37 Correct 46 ms 73768 KB Output is correct
38 Correct 59 ms 73768 KB Output is correct
39 Correct 56 ms 73768 KB Output is correct
40 Correct 59 ms 74032 KB Output is correct
41 Correct 53 ms 74032 KB Output is correct
42 Correct 59 ms 73900 KB Output is correct
43 Correct 66 ms 74032 KB Output is correct
44 Correct 63 ms 74032 KB Output is correct
45 Correct 63 ms 74032 KB Output is correct
46 Correct 56 ms 73900 KB Output is correct
47 Correct 46 ms 74032 KB Output is correct
48 Correct 449 ms 85780 KB Output is correct
49 Correct 479 ms 85780 KB Output is correct
50 Correct 496 ms 85912 KB Output is correct
51 Correct 443 ms 85780 KB Output is correct
52 Correct 459 ms 83600 KB Output is correct
53 Correct 463 ms 84280 KB Output is correct
54 Correct 446 ms 82312 KB Output is correct
55 Correct 446 ms 81924 KB Output is correct
56 Correct 443 ms 81396 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 72712 KB Output is correct
2 Correct 16 ms 72712 KB Output is correct
3 Correct 16 ms 72712 KB Output is correct
4 Correct 9 ms 72712 KB Output is correct
5 Correct 6 ms 72712 KB Output is correct
6 Correct 6 ms 72712 KB Output is correct
7 Correct 9 ms 72712 KB Output is correct
8 Correct 9 ms 72712 KB Output is correct
9 Correct 6 ms 72712 KB Output is correct
10 Correct 9 ms 72712 KB Output is correct
11 Correct 9 ms 72712 KB Output is correct
12 Correct 9 ms 72712 KB Output is correct
13 Correct 19 ms 72712 KB Output is correct
14 Correct 6 ms 72712 KB Output is correct
15 Correct 3 ms 72712 KB Output is correct
16 Correct 9 ms 72712 KB Output is correct
17 Correct 13 ms 72712 KB Output is correct
18 Correct 9 ms 72712 KB Output is correct
19 Correct 6 ms 72712 KB Output is correct
20 Correct 16 ms 72712 KB Output is correct
21 Correct 13 ms 72712 KB Output is correct
22 Correct 9 ms 72712 KB Output is correct
23 Correct 13 ms 72712 KB Output is correct
24 Correct 13 ms 72712 KB Output is correct
25 Correct 16 ms 72712 KB Output is correct
26 Correct 6 ms 72712 KB Output is correct
27 Correct 53 ms 74176 KB Output is correct
28 Correct 46 ms 73888 KB Output is correct
29 Correct 49 ms 74072 KB Output is correct
30 Correct 56 ms 73492 KB Output is correct
31 Correct 53 ms 74208 KB Output is correct
32 Correct 46 ms 73884 KB Output is correct
33 Correct 56 ms 74076 KB Output is correct
34 Correct 53 ms 73492 KB Output is correct
35 Correct 53 ms 73768 KB Output is correct
36 Correct 56 ms 73768 KB Output is correct
37 Correct 46 ms 73768 KB Output is correct
38 Correct 59 ms 73768 KB Output is correct
39 Correct 56 ms 73768 KB Output is correct
40 Correct 59 ms 74032 KB Output is correct
41 Correct 53 ms 74032 KB Output is correct
42 Correct 59 ms 73900 KB Output is correct
43 Correct 66 ms 74032 KB Output is correct
44 Correct 63 ms 74032 KB Output is correct
45 Correct 63 ms 74032 KB Output is correct
46 Correct 56 ms 73900 KB Output is correct
47 Correct 46 ms 74032 KB Output is correct
48 Correct 449 ms 85780 KB Output is correct
49 Correct 479 ms 85780 KB Output is correct
50 Correct 496 ms 85912 KB Output is correct
51 Correct 443 ms 85780 KB Output is correct
52 Correct 459 ms 83600 KB Output is correct
53 Correct 463 ms 84280 KB Output is correct
54 Correct 446 ms 82312 KB Output is correct
55 Correct 446 ms 81924 KB Output is correct
56 Correct 443 ms 81396 KB Output is correct
57 Correct 1816 ms 135280 KB Output is correct
58 Correct 1633 ms 110332 KB Output is correct
59 Correct 1653 ms 110200 KB Output is correct
60 Correct 1693 ms 116404 KB Output is correct
61 Correct 1689 ms 116536 KB Output is correct
62 Correct 869 ms 97744 KB Output is correct
63 Correct 1206 ms 104060 KB Output is correct
64 Correct 1133 ms 100120 KB Output is correct
65 Correct 673 ms 89704 KB Output is correct