Submission #155472

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
155472	2019-09-28T16:01:44 Z	TadijaSebez	Rope (JOI17_rope)	C++11	100 / 100	2303 ms	81876 KB

rope

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=1000050;
const int M=2*N;
struct SegmentTree
{
	int mx[M];
	SegmentTree(){}
	void Set(int i, int f){ mx[i+=N]+=f;for(i>>=1;i;i>>=1) mx[i]=max(mx[i<<1],mx[i<<1|1]);}
	int Get(int l, int r)
	{
		int ans=0;
		for(l+=N,r+=N;l<=r;l>>=1,r>>=1)
		{
			if(l%2==1) ans=max(ans,mx[l++]);
			if(r%2==0) ans=max(ans,mx[r--]);
		}
		return ans;
	}
} ST[2];
int a[N];
vector<int> pos[N];
int main()
{
	int n,k;
	scanf("%i %i",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%i",&a[i]);
		ST[0].Set(a[i],1);
		ST[1].Set(a[i],1);
		pos[a[i]].pb(i);
	}
	for(int i=1;i<=k;i++)
	{
		vector<int> del[2];
		for(int x:pos[i])
		{
			del[0].pb(x);
			del[1].pb(x);
			int y;
			if(x%2==1) y=x+1;
			else y=x-1;
			if(y>0 && y<=n && a[y]!=i) del[0].pb(y);
			if(x%2==0) y=x+1;
			else y=x-1;
			if(y>0 && y<=n && a[y]!=i) del[1].pb(y);
		}
		for(int x:del[0]) ST[0].Set(a[x],-1);
		for(int x:del[1]) ST[1].Set(a[x],-1);
		int ans=n-pos[i].size()-max(ST[0].Get(1,k),ST[1].Get(1,k));
		printf("%i\n",ans);
		for(int x:del[0]) ST[0].Set(a[x],1);
		for(int x:del[1]) ST[1].Set(a[x],1);
	}
	return 0;
}

Compilation message

rope.cpp: In function 'int main()':
rope.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~
rope.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i",&a[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	23928 KB	Output is correct
2	Correct	25 ms	24056 KB	Output is correct
3	Correct	24 ms	23928 KB	Output is correct
4	Correct	24 ms	23928 KB	Output is correct
5	Correct	24 ms	23972 KB	Output is correct
6	Correct	26 ms	24056 KB	Output is correct
7	Correct	24 ms	23928 KB	Output is correct
8	Correct	24 ms	23928 KB	Output is correct
9	Correct	25 ms	23976 KB	Output is correct
10	Correct	24 ms	23928 KB	Output is correct
11	Correct	24 ms	23928 KB	Output is correct
12	Correct	24 ms	23928 KB	Output is correct
13	Correct	24 ms	23928 KB	Output is correct
14	Correct	24 ms	23928 KB	Output is correct
15	Correct	24 ms	23932 KB	Output is correct
16	Correct	24 ms	23932 KB	Output is correct
17	Correct	24 ms	23928 KB	Output is correct
18	Correct	24 ms	23900 KB	Output is correct
19	Correct	28 ms	23904 KB	Output is correct
20	Correct	24 ms	23928 KB	Output is correct
21	Correct	24 ms	23992 KB	Output is correct
22	Correct	24 ms	23928 KB	Output is correct
23	Correct	24 ms	23928 KB	Output is correct
24	Correct	24 ms	23928 KB	Output is correct
25	Correct	36 ms	23928 KB	Output is correct
26	Correct	30 ms	24056 KB	Output is correct

Subtask #2
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	23928 KB	Output is correct
2	Correct	25 ms	24056 KB	Output is correct
3	Correct	24 ms	23928 KB	Output is correct
4	Correct	24 ms	23928 KB	Output is correct
5	Correct	24 ms	23972 KB	Output is correct
6	Correct	26 ms	24056 KB	Output is correct
7	Correct	24 ms	23928 KB	Output is correct
8	Correct	24 ms	23928 KB	Output is correct
9	Correct	25 ms	23976 KB	Output is correct
10	Correct	24 ms	23928 KB	Output is correct
11	Correct	24 ms	23928 KB	Output is correct
12	Correct	24 ms	23928 KB	Output is correct
13	Correct	24 ms	23928 KB	Output is correct
14	Correct	24 ms	23928 KB	Output is correct
15	Correct	24 ms	23932 KB	Output is correct
16	Correct	24 ms	23932 KB	Output is correct
17	Correct	24 ms	23928 KB	Output is correct
18	Correct	24 ms	23900 KB	Output is correct
19	Correct	28 ms	23904 KB	Output is correct
20	Correct	24 ms	23928 KB	Output is correct
21	Correct	24 ms	23992 KB	Output is correct
22	Correct	24 ms	23928 KB	Output is correct
23	Correct	24 ms	23928 KB	Output is correct
24	Correct	24 ms	23928 KB	Output is correct
25	Correct	36 ms	23928 KB	Output is correct
26	Correct	30 ms	24056 KB	Output is correct
27	Correct	82 ms	25412 KB	Output is correct
28	Correct	79 ms	25512 KB	Output is correct
29	Correct	83 ms	25240 KB	Output is correct
30	Correct	82 ms	25596 KB	Output is correct
31	Correct	83 ms	25280 KB	Output is correct
32	Correct	81 ms	25464 KB	Output is correct
33	Correct	89 ms	25348 KB	Output is correct
34	Correct	82 ms	25724 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	23928 KB	Output is correct
2	Correct	25 ms	24056 KB	Output is correct
3	Correct	24 ms	23928 KB	Output is correct
4	Correct	24 ms	23928 KB	Output is correct
5	Correct	24 ms	23972 KB	Output is correct
6	Correct	26 ms	24056 KB	Output is correct
7	Correct	24 ms	23928 KB	Output is correct
8	Correct	24 ms	23928 KB	Output is correct
9	Correct	25 ms	23976 KB	Output is correct
10	Correct	24 ms	23928 KB	Output is correct
11	Correct	24 ms	23928 KB	Output is correct
12	Correct	24 ms	23928 KB	Output is correct
13	Correct	24 ms	23928 KB	Output is correct
14	Correct	24 ms	23928 KB	Output is correct
15	Correct	24 ms	23932 KB	Output is correct
16	Correct	24 ms	23932 KB	Output is correct
17	Correct	24 ms	23928 KB	Output is correct
18	Correct	24 ms	23900 KB	Output is correct
19	Correct	28 ms	23904 KB	Output is correct
20	Correct	24 ms	23928 KB	Output is correct
21	Correct	24 ms	23992 KB	Output is correct
22	Correct	24 ms	23928 KB	Output is correct
23	Correct	24 ms	23928 KB	Output is correct
24	Correct	24 ms	23928 KB	Output is correct
25	Correct	36 ms	23928 KB	Output is correct
26	Correct	30 ms	24056 KB	Output is correct
27	Correct	82 ms	25412 KB	Output is correct
28	Correct	79 ms	25512 KB	Output is correct
29	Correct	83 ms	25240 KB	Output is correct
30	Correct	82 ms	25596 KB	Output is correct
31	Correct	83 ms	25280 KB	Output is correct
32	Correct	81 ms	25464 KB	Output is correct
33	Correct	89 ms	25348 KB	Output is correct
34	Correct	82 ms	25724 KB	Output is correct
35	Correct	91 ms	24932 KB	Output is correct
36	Correct	90 ms	24824 KB	Output is correct
37	Correct	116 ms	24908 KB	Output is correct
38	Correct	86 ms	24824 KB	Output is correct
39	Correct	90 ms	24828 KB	Output is correct
40	Correct	87 ms	24952 KB	Output is correct
41	Correct	88 ms	24952 KB	Output is correct
42	Correct	96 ms	24952 KB	Output is correct
43	Correct	88 ms	25108 KB	Output is correct
44	Correct	91 ms	24952 KB	Output is correct
45	Correct	105 ms	25144 KB	Output is correct
46	Correct	94 ms	25000 KB	Output is correct
47	Correct	95 ms	24952 KB	Output is correct

Subtask #4
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	23928 KB	Output is correct
2	Correct	25 ms	24056 KB	Output is correct
3	Correct	24 ms	23928 KB	Output is correct
4	Correct	24 ms	23928 KB	Output is correct
5	Correct	24 ms	23972 KB	Output is correct
6	Correct	26 ms	24056 KB	Output is correct
7	Correct	24 ms	23928 KB	Output is correct
8	Correct	24 ms	23928 KB	Output is correct
9	Correct	25 ms	23976 KB	Output is correct
10	Correct	24 ms	23928 KB	Output is correct
11	Correct	24 ms	23928 KB	Output is correct
12	Correct	24 ms	23928 KB	Output is correct
13	Correct	24 ms	23928 KB	Output is correct
14	Correct	24 ms	23928 KB	Output is correct
15	Correct	24 ms	23932 KB	Output is correct
16	Correct	24 ms	23932 KB	Output is correct
17	Correct	24 ms	23928 KB	Output is correct
18	Correct	24 ms	23900 KB	Output is correct
19	Correct	28 ms	23904 KB	Output is correct
20	Correct	24 ms	23928 KB	Output is correct
21	Correct	24 ms	23992 KB	Output is correct
22	Correct	24 ms	23928 KB	Output is correct
23	Correct	24 ms	23928 KB	Output is correct
24	Correct	24 ms	23928 KB	Output is correct
25	Correct	36 ms	23928 KB	Output is correct
26	Correct	30 ms	24056 KB	Output is correct
27	Correct	82 ms	25412 KB	Output is correct
28	Correct	79 ms	25512 KB	Output is correct
29	Correct	83 ms	25240 KB	Output is correct
30	Correct	82 ms	25596 KB	Output is correct
31	Correct	83 ms	25280 KB	Output is correct
32	Correct	81 ms	25464 KB	Output is correct
33	Correct	89 ms	25348 KB	Output is correct
34	Correct	82 ms	25724 KB	Output is correct
35	Correct	91 ms	24932 KB	Output is correct
36	Correct	90 ms	24824 KB	Output is correct
37	Correct	116 ms	24908 KB	Output is correct
38	Correct	86 ms	24824 KB	Output is correct
39	Correct	90 ms	24828 KB	Output is correct
40	Correct	87 ms	24952 KB	Output is correct
41	Correct	88 ms	24952 KB	Output is correct
42	Correct	96 ms	24952 KB	Output is correct
43	Correct	88 ms	25108 KB	Output is correct
44	Correct	91 ms	24952 KB	Output is correct
45	Correct	105 ms	25144 KB	Output is correct
46	Correct	94 ms	25000 KB	Output is correct
47	Correct	95 ms	24952 KB	Output is correct
48	Correct	753 ms	34684 KB	Output is correct
49	Correct	750 ms	34540 KB	Output is correct
50	Correct	826 ms	34656 KB	Output is correct
51	Correct	776 ms	34576 KB	Output is correct
52	Correct	718 ms	33616 KB	Output is correct
53	Correct	733 ms	34052 KB	Output is correct
54	Correct	700 ms	33016 KB	Output is correct
55	Correct	700 ms	32984 KB	Output is correct
56	Correct	694 ms	32480 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	23928 KB	Output is correct
2	Correct	25 ms	24056 KB	Output is correct
3	Correct	24 ms	23928 KB	Output is correct
4	Correct	24 ms	23928 KB	Output is correct
5	Correct	24 ms	23972 KB	Output is correct
6	Correct	26 ms	24056 KB	Output is correct
7	Correct	24 ms	23928 KB	Output is correct
8	Correct	24 ms	23928 KB	Output is correct
9	Correct	25 ms	23976 KB	Output is correct
10	Correct	24 ms	23928 KB	Output is correct
11	Correct	24 ms	23928 KB	Output is correct
12	Correct	24 ms	23928 KB	Output is correct
13	Correct	24 ms	23928 KB	Output is correct
14	Correct	24 ms	23928 KB	Output is correct
15	Correct	24 ms	23932 KB	Output is correct
16	Correct	24 ms	23932 KB	Output is correct
17	Correct	24 ms	23928 KB	Output is correct
18	Correct	24 ms	23900 KB	Output is correct
19	Correct	28 ms	23904 KB	Output is correct
20	Correct	24 ms	23928 KB	Output is correct
21	Correct	24 ms	23992 KB	Output is correct
22	Correct	24 ms	23928 KB	Output is correct
23	Correct	24 ms	23928 KB	Output is correct
24	Correct	24 ms	23928 KB	Output is correct
25	Correct	36 ms	23928 KB	Output is correct
26	Correct	30 ms	24056 KB	Output is correct
27	Correct	82 ms	25412 KB	Output is correct
28	Correct	79 ms	25512 KB	Output is correct
29	Correct	83 ms	25240 KB	Output is correct
30	Correct	82 ms	25596 KB	Output is correct
31	Correct	83 ms	25280 KB	Output is correct
32	Correct	81 ms	25464 KB	Output is correct
33	Correct	89 ms	25348 KB	Output is correct
34	Correct	82 ms	25724 KB	Output is correct
35	Correct	91 ms	24932 KB	Output is correct
36	Correct	90 ms	24824 KB	Output is correct
37	Correct	116 ms	24908 KB	Output is correct
38	Correct	86 ms	24824 KB	Output is correct
39	Correct	90 ms	24828 KB	Output is correct
40	Correct	87 ms	24952 KB	Output is correct
41	Correct	88 ms	24952 KB	Output is correct
42	Correct	96 ms	24952 KB	Output is correct
43	Correct	88 ms	25108 KB	Output is correct
44	Correct	91 ms	24952 KB	Output is correct
45	Correct	105 ms	25144 KB	Output is correct
46	Correct	94 ms	25000 KB	Output is correct
47	Correct	95 ms	24952 KB	Output is correct
48	Correct	753 ms	34684 KB	Output is correct
49	Correct	750 ms	34540 KB	Output is correct
50	Correct	826 ms	34656 KB	Output is correct
51	Correct	776 ms	34576 KB	Output is correct
52	Correct	718 ms	33616 KB	Output is correct
53	Correct	733 ms	34052 KB	Output is correct
54	Correct	700 ms	33016 KB	Output is correct
55	Correct	700 ms	32984 KB	Output is correct
56	Correct	694 ms	32480 KB	Output is correct
57	Correct	2303 ms	81876 KB	Output is correct
58	Correct	1985 ms	63624 KB	Output is correct
59	Correct	2017 ms	63488 KB	Output is correct
60	Correct	2090 ms	68824 KB	Output is correct
61	Correct	2116 ms	68872 KB	Output is correct
62	Correct	1302 ms	50612 KB	Output is correct
63	Correct	1611 ms	56388 KB	Output is correct
64	Correct	1396 ms	52728 KB	Output is correct
65	Correct	1039 ms	43228 KB	Output is correct

Submission #155472

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 30.0 / 30.0

Subtask #3 10.0 / 10.0

Subtask #4 25.0 / 25.0

Subtask #5 20.0 / 20.0

Subtask #1
15.0 / 15.0

Subtask #2
30.0 / 30.0

Subtask #3
10.0 / 10.0

Subtask #4
25.0 / 25.0

Subtask #5
20.0 / 20.0