Submission #128144

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
128144	2019-07-10T13:04:24 Z	TadijaSebez	Global Warming (CEOI18_glo)	C++11	100 / 100	451 ms	13572 KB

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=200050;
const int lim=2*N;
const int M=2*lim;
int hi[N],lo[N],l[N],r[N];
vector<int> id;
int ls[M],rs[M],mx[M],tsz,root;
void Set(int &c, int ss, int se, int qi, int x)
{
	if(!c) c=++tsz;
	mx[c]=max(mx[c],x);
	if(ss==se) return;
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls[c],ss,mid,qi,x);
	else Set(rs[c],mid+1,se,qi,x);
}
int Get(int c, int ss, int se, int qs, int qe)
{
	if(qs>qe || qs>se || ss>qe) return 0;
	if(qs<=ss && qe>=se) return mx[c];
	int mid=ss+se>>1;
	return max(Get(ls[c],ss,mid,qs,qe),Get(rs[c],mid+1,se,qs,qe));
}
void Clear()
{
	for(int i=1;i<=tsz;i++) ls[i]=rs[i]=mx[i]=0;
	tsz=root=0;
}
int main()
{
	int n,x;
	scanf("%i %i",&n,&x);
	for(int i=1;i<=n;i++)
	{
		scanf("%i",&hi[i]);
		lo[i]=hi[i]-x;
		id.pb(hi[i]);
		id.pb(lo[i]);
	}
	sort(id.begin(),id.end());
	id.resize(unique(id.begin(),id.end())-id.begin());
	for(int i=1;i<=n;i++)
	{
		hi[i]=lower_bound(id.begin(),id.end(),hi[i])-id.begin()+1;
		lo[i]=lower_bound(id.begin(),id.end(),lo[i])-id.begin()+1;
	}
	for(int i=1;i<=n;i++)
	{
		l[i]=Get(root,1,lim,1,hi[i]-1)+1;
		Set(root,1,lim,lo[i],Get(root,1,lim,1,lo[i]-1)+1);
	}
	Clear();
	for(int i=n;i>=1;i--)
	{
		r[i]=Get(root,1,lim,hi[i]+1,lim)+1;
		Set(root,1,lim,hi[i],r[i]);
	}
	int ans=0;
	for(int i=1;i<=n;i++) ans=max(ans,l[i]+r[i]-1);
	printf("%i\n",ans);
	return 0;
}

Compilation message

glo.cpp: In function 'void Set(int&, int, int, int, int)':
glo.cpp:15:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
glo.cpp: In function 'int Get(int, int, int, int, int)':
glo.cpp:23:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
glo.cpp: In function 'int main()':
glo.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&x);
  ~~~~~^~~~~~~~~~~~~~~
glo.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i",&hi[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	3 ms	376 KB	Output is correct
9	Correct	2 ms	380 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	3 ms	376 KB	Output is correct
9	Correct	2 ms	380 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	3 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	3 ms	376 KB	Output is correct
18	Correct	2 ms	380 KB	Output is correct

Subtask #3
13.0 / 13.0

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

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	416 ms	11732 KB	Output is correct
2	Correct	408 ms	11848 KB	Output is correct
3	Correct	410 ms	11800 KB	Output is correct
4	Correct	439 ms	11820 KB	Output is correct
5	Correct	208 ms	8676 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	91 ms	3956 KB	Output is correct
2	Correct	89 ms	4048 KB	Output is correct
3	Correct	90 ms	4080 KB	Output is correct
4	Correct	56 ms	2876 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	58 ms	2804 KB	Output is correct
7	Correct	74 ms	3696 KB	Output is correct

Subtask #6
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	197 ms	6120 KB	Output is correct
2	Correct	192 ms	6224 KB	Output is correct
3	Correct	436 ms	11716 KB	Output is correct
4	Correct	217 ms	8744 KB	Output is correct
5	Correct	127 ms	5712 KB	Output is correct
6	Correct	232 ms	10596 KB	Output is correct
7	Correct	237 ms	11240 KB	Output is correct
8	Correct	153 ms	6252 KB	Output is correct

Subtask #7
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	3 ms	376 KB	Output is correct
9	Correct	2 ms	380 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	3 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	3 ms	376 KB	Output is correct
18	Correct	2 ms	380 KB	Output is correct
19	Correct	3 ms	376 KB	Output is correct
20	Correct	3 ms	504 KB	Output is correct
21	Correct	4 ms	376 KB	Output is correct
22	Correct	4 ms	376 KB	Output is correct
23	Correct	3 ms	424 KB	Output is correct
24	Correct	3 ms	376 KB	Output is correct
25	Correct	2 ms	380 KB	Output is correct
26	Correct	3 ms	376 KB	Output is correct
27	Correct	416 ms	11732 KB	Output is correct
28	Correct	408 ms	11848 KB	Output is correct
29	Correct	410 ms	11800 KB	Output is correct
30	Correct	439 ms	11820 KB	Output is correct
31	Correct	208 ms	8676 KB	Output is correct
32	Correct	91 ms	3956 KB	Output is correct
33	Correct	89 ms	4048 KB	Output is correct
34	Correct	90 ms	4080 KB	Output is correct
35	Correct	56 ms	2876 KB	Output is correct
36	Correct	2 ms	376 KB	Output is correct
37	Correct	58 ms	2804 KB	Output is correct
38	Correct	74 ms	3696 KB	Output is correct
39	Correct	197 ms	6120 KB	Output is correct
40	Correct	192 ms	6224 KB	Output is correct
41	Correct	436 ms	11716 KB	Output is correct
42	Correct	217 ms	8744 KB	Output is correct
43	Correct	127 ms	5712 KB	Output is correct
44	Correct	232 ms	10596 KB	Output is correct
45	Correct	237 ms	11240 KB	Output is correct
46	Correct	153 ms	6252 KB	Output is correct
47	Correct	194 ms	7328 KB	Output is correct
48	Correct	202 ms	7340 KB	Output is correct
49	Correct	451 ms	13572 KB	Output is correct
50	Correct	218 ms	9876 KB	Output is correct
51	Correct	173 ms	7268 KB	Output is correct
52	Correct	250 ms	11256 KB	Output is correct
53	Correct	246 ms	11240 KB	Output is correct
54	Correct	248 ms	11872 KB	Output is correct
55	Correct	331 ms	13284 KB	Output is correct

Submission #128144

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 13.0 / 13.0

Subtask #4 10.0 / 10.0

Subtask #5 20.0 / 20.0

Subtask #6 17.0 / 17.0

Subtask #7 25.0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
13.0 / 13.0

Subtask #4
10.0 / 10.0

Subtask #5
20.0 / 20.0

Subtask #6
17.0 / 17.0

Subtask #7
25.0 / 25.0