Submission #155471

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
155471	2019-09-28T15:59:43 Z	TadijaSebez	Rope (JOI17_rope)	C++11	80 / 100	2500 ms	85608 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) del[0].pb(y);
			if(x%2==0) y=x+1;
			else y=x-1;
			if(y>0 && y<=n) del[1].pb(y);
		}
		sort(del[0].begin(),del[0].end());
		del[0].erase(unique(del[0].begin(),del[0].end()),del[0].end());
		sort(del[1].begin(),del[1].end());
		del[1].erase(unique(del[1].begin(),del[1].end()),del[1].end());
		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	24 ms	23928 KB	Output is correct
3	Correct	24 ms	23928 KB	Output is correct
4	Correct	25 ms	23932 KB	Output is correct
5	Correct	24 ms	23928 KB	Output is correct
6	Correct	24 ms	23928 KB	Output is correct
7	Correct	23 ms	24056 KB	Output is correct
8	Correct	24 ms	23972 KB	Output is correct
9	Correct	24 ms	23928 KB	Output is correct
10	Correct	24 ms	23900 KB	Output is correct
11	Correct	25 ms	24028 KB	Output is correct
12	Correct	25 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	23928 KB	Output is correct
16	Correct	24 ms	23928 KB	Output is correct
17	Correct	24 ms	23928 KB	Output is correct
18	Correct	25 ms	23928 KB	Output is correct
19	Correct	24 ms	24056 KB	Output is correct
20	Correct	24 ms	23928 KB	Output is correct
21	Correct	24 ms	23928 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	24 ms	23928 KB	Output is correct
26	Correct	24 ms	23928 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	24 ms	23928 KB	Output is correct
3	Correct	24 ms	23928 KB	Output is correct
4	Correct	25 ms	23932 KB	Output is correct
5	Correct	24 ms	23928 KB	Output is correct
6	Correct	24 ms	23928 KB	Output is correct
7	Correct	23 ms	24056 KB	Output is correct
8	Correct	24 ms	23972 KB	Output is correct
9	Correct	24 ms	23928 KB	Output is correct
10	Correct	24 ms	23900 KB	Output is correct
11	Correct	25 ms	24028 KB	Output is correct
12	Correct	25 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	23928 KB	Output is correct
16	Correct	24 ms	23928 KB	Output is correct
17	Correct	24 ms	23928 KB	Output is correct
18	Correct	25 ms	23928 KB	Output is correct
19	Correct	24 ms	24056 KB	Output is correct
20	Correct	24 ms	23928 KB	Output is correct
21	Correct	24 ms	23928 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	24 ms	23928 KB	Output is correct
26	Correct	24 ms	23928 KB	Output is correct
27	Correct	91 ms	25444 KB	Output is correct
28	Correct	88 ms	25840 KB	Output is correct
29	Correct	96 ms	25484 KB	Output is correct
30	Correct	91 ms	25704 KB	Output is correct
31	Correct	91 ms	25500 KB	Output is correct
32	Correct	90 ms	25800 KB	Output is correct
33	Correct	91 ms	25592 KB	Output is correct
34	Correct	92 ms	25916 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	24 ms	23928 KB	Output is correct
3	Correct	24 ms	23928 KB	Output is correct
4	Correct	25 ms	23932 KB	Output is correct
5	Correct	24 ms	23928 KB	Output is correct
6	Correct	24 ms	23928 KB	Output is correct
7	Correct	23 ms	24056 KB	Output is correct
8	Correct	24 ms	23972 KB	Output is correct
9	Correct	24 ms	23928 KB	Output is correct
10	Correct	24 ms	23900 KB	Output is correct
11	Correct	25 ms	24028 KB	Output is correct
12	Correct	25 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	23928 KB	Output is correct
16	Correct	24 ms	23928 KB	Output is correct
17	Correct	24 ms	23928 KB	Output is correct
18	Correct	25 ms	23928 KB	Output is correct
19	Correct	24 ms	24056 KB	Output is correct
20	Correct	24 ms	23928 KB	Output is correct
21	Correct	24 ms	23928 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	24 ms	23928 KB	Output is correct
26	Correct	24 ms	23928 KB	Output is correct
27	Correct	91 ms	25444 KB	Output is correct
28	Correct	88 ms	25840 KB	Output is correct
29	Correct	96 ms	25484 KB	Output is correct
30	Correct	91 ms	25704 KB	Output is correct
31	Correct	91 ms	25500 KB	Output is correct
32	Correct	90 ms	25800 KB	Output is correct
33	Correct	91 ms	25592 KB	Output is correct
34	Correct	92 ms	25916 KB	Output is correct
35	Correct	98 ms	25256 KB	Output is correct
36	Correct	99 ms	25308 KB	Output is correct
37	Correct	99 ms	25280 KB	Output is correct
38	Correct	99 ms	25336 KB	Output is correct
39	Correct	97 ms	25208 KB	Output is correct
40	Correct	94 ms	25340 KB	Output is correct
41	Correct	95 ms	25404 KB	Output is correct
42	Correct	95 ms	25340 KB	Output is correct
43	Correct	95 ms	25336 KB	Output is correct
44	Correct	99 ms	25428 KB	Output is correct
45	Correct	99 ms	25408 KB	Output is correct
46	Correct	93 ms	25336 KB	Output is correct
47	Correct	94 ms	25436 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	24 ms	23928 KB	Output is correct
3	Correct	24 ms	23928 KB	Output is correct
4	Correct	25 ms	23932 KB	Output is correct
5	Correct	24 ms	23928 KB	Output is correct
6	Correct	24 ms	23928 KB	Output is correct
7	Correct	23 ms	24056 KB	Output is correct
8	Correct	24 ms	23972 KB	Output is correct
9	Correct	24 ms	23928 KB	Output is correct
10	Correct	24 ms	23900 KB	Output is correct
11	Correct	25 ms	24028 KB	Output is correct
12	Correct	25 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	23928 KB	Output is correct
16	Correct	24 ms	23928 KB	Output is correct
17	Correct	24 ms	23928 KB	Output is correct
18	Correct	25 ms	23928 KB	Output is correct
19	Correct	24 ms	24056 KB	Output is correct
20	Correct	24 ms	23928 KB	Output is correct
21	Correct	24 ms	23928 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	24 ms	23928 KB	Output is correct
26	Correct	24 ms	23928 KB	Output is correct
27	Correct	91 ms	25444 KB	Output is correct
28	Correct	88 ms	25840 KB	Output is correct
29	Correct	96 ms	25484 KB	Output is correct
30	Correct	91 ms	25704 KB	Output is correct
31	Correct	91 ms	25500 KB	Output is correct
32	Correct	90 ms	25800 KB	Output is correct
33	Correct	91 ms	25592 KB	Output is correct
34	Correct	92 ms	25916 KB	Output is correct
35	Correct	98 ms	25256 KB	Output is correct
36	Correct	99 ms	25308 KB	Output is correct
37	Correct	99 ms	25280 KB	Output is correct
38	Correct	99 ms	25336 KB	Output is correct
39	Correct	97 ms	25208 KB	Output is correct
40	Correct	94 ms	25340 KB	Output is correct
41	Correct	95 ms	25404 KB	Output is correct
42	Correct	95 ms	25340 KB	Output is correct
43	Correct	95 ms	25336 KB	Output is correct
44	Correct	99 ms	25428 KB	Output is correct
45	Correct	99 ms	25408 KB	Output is correct
46	Correct	93 ms	25336 KB	Output is correct
47	Correct	94 ms	25436 KB	Output is correct
48	Correct	869 ms	39128 KB	Output is correct
49	Correct	900 ms	38864 KB	Output is correct
50	Correct	869 ms	39004 KB	Output is correct
51	Correct	863 ms	38764 KB	Output is correct
52	Correct	839 ms	37472 KB	Output is correct
53	Correct	833 ms	38264 KB	Output is correct
54	Correct	796 ms	37248 KB	Output is correct
55	Correct	802 ms	37196 KB	Output is correct
56	Correct	820 ms	36760 KB	Output is correct

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	23928 KB	Output is correct
2	Correct	24 ms	23928 KB	Output is correct
3	Correct	24 ms	23928 KB	Output is correct
4	Correct	25 ms	23932 KB	Output is correct
5	Correct	24 ms	23928 KB	Output is correct
6	Correct	24 ms	23928 KB	Output is correct
7	Correct	23 ms	24056 KB	Output is correct
8	Correct	24 ms	23972 KB	Output is correct
9	Correct	24 ms	23928 KB	Output is correct
10	Correct	24 ms	23900 KB	Output is correct
11	Correct	25 ms	24028 KB	Output is correct
12	Correct	25 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	23928 KB	Output is correct
16	Correct	24 ms	23928 KB	Output is correct
17	Correct	24 ms	23928 KB	Output is correct
18	Correct	25 ms	23928 KB	Output is correct
19	Correct	24 ms	24056 KB	Output is correct
20	Correct	24 ms	23928 KB	Output is correct
21	Correct	24 ms	23928 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	24 ms	23928 KB	Output is correct
26	Correct	24 ms	23928 KB	Output is correct
27	Correct	91 ms	25444 KB	Output is correct
28	Correct	88 ms	25840 KB	Output is correct
29	Correct	96 ms	25484 KB	Output is correct
30	Correct	91 ms	25704 KB	Output is correct
31	Correct	91 ms	25500 KB	Output is correct
32	Correct	90 ms	25800 KB	Output is correct
33	Correct	91 ms	25592 KB	Output is correct
34	Correct	92 ms	25916 KB	Output is correct
35	Correct	98 ms	25256 KB	Output is correct
36	Correct	99 ms	25308 KB	Output is correct
37	Correct	99 ms	25280 KB	Output is correct
38	Correct	99 ms	25336 KB	Output is correct
39	Correct	97 ms	25208 KB	Output is correct
40	Correct	94 ms	25340 KB	Output is correct
41	Correct	95 ms	25404 KB	Output is correct
42	Correct	95 ms	25340 KB	Output is correct
43	Correct	95 ms	25336 KB	Output is correct
44	Correct	99 ms	25428 KB	Output is correct
45	Correct	99 ms	25408 KB	Output is correct
46	Correct	93 ms	25336 KB	Output is correct
47	Correct	94 ms	25436 KB	Output is correct
48	Correct	869 ms	39128 KB	Output is correct
49	Correct	900 ms	38864 KB	Output is correct
50	Correct	869 ms	39004 KB	Output is correct
51	Correct	863 ms	38764 KB	Output is correct
52	Correct	839 ms	37472 KB	Output is correct
53	Correct	833 ms	38264 KB	Output is correct
54	Correct	796 ms	37248 KB	Output is correct
55	Correct	802 ms	37196 KB	Output is correct
56	Correct	820 ms	36760 KB	Output is correct
57	Execution timed out	2518 ms	85608 KB	Time limit exceeded
58	Halted	0 ms	0 KB	-

Submission #155471

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 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
0 / 20.0