답안 #258562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
258562	2020-08-06T06:56:22 Z	Berted	Global Warming (CEOI18_glo)	C++14	100 / 100	233 ms	5616 KB

glo

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#define pii pair<int, int>
#define ppi pair<pii, int>
#define fst first
#define snd second
using namespace std;

int n, x, ar[200001];
vector<int> coord;
int fwk[2][200001] = {};

inline void upd(int t, int x, int v)
{
	x = prev(upper_bound(coord.begin(), coord.end(), x)) - coord.begin();
	for (; x < coord.size(); x += x & (-x)) {fwk[t][x] = max(fwk[t][x], v);}
}

inline int qry(int t, int x)
{
	int ret = 0;
	x = prev(upper_bound(coord.begin(), coord.end(), x)) - coord.begin();
	for (; x; x -= x & (-x)) {ret = max(ret, fwk[t][x]);}
	return ret;
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> x;
	coord.push_back(0);
	for (int i = 0; i < n; i++)
	{
		cin >> ar[i];
		coord.push_back(ar[i]);
	}
	sort(coord.begin(), coord.end());
	coord.resize(unique(coord.begin(), coord.end()) - coord.begin());
	int res = 0;
	for (int i = 0; i < n; i++)
	{
		int ret = qry(0, ar[i] + x - 1) + 1;
		upd(1, ar[i], ret);
		res = max(ret, res);

		ret = qry(0, ar[i] - 1) + 1;
		upd(0, ar[i], ret);
		res = max(ret, res);
		
		ret = qry(1, ar[i] - 1) + 1;
		upd(1, ar[i], ret);
		res = max(ret, res);
	}
	cout << res << "\n";
	return 0;
}

Compilation message

glo.cpp: In function 'void upd(int, int, int)':
glo.cpp:18:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (; x < coord.size(); x += x & (-x)) {fwk[t][x] = max(fwk[t][x], v);}
         ~~^~~~~~~~~~~~~~

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	0 ms	384 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	0 ms	384 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	0 ms	384 KB	Output is correct
18	Correct	0 ms	384 KB	Output is correct

Subtask #3

13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	0 ms	384 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	0 ms	384 KB	Output is correct
18	Correct	0 ms	384 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	1 ms	384 KB	Output is correct
21	Correct	1 ms	384 KB	Output is correct
22	Correct	1 ms	384 KB	Output is correct
23	Correct	1 ms	384 KB	Output is correct
24	Correct	1 ms	384 KB	Output is correct
25	Correct	1 ms	384 KB	Output is correct
26	Correct	1 ms	384 KB	Output is correct

Subtask #4

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	225 ms	3568 KB	Output is correct
2	Correct	225 ms	3568 KB	Output is correct
3	Correct	227 ms	3564 KB	Output is correct
4	Correct	233 ms	3552 KB	Output is correct
5	Correct	109 ms	2800 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	51 ms	1280 KB	Output is correct
2	Correct	50 ms	1792 KB	Output is correct
3	Correct	51 ms	1792 KB	Output is correct
4	Correct	25 ms	1400 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	26 ms	1408 KB	Output is correct
7	Correct	42 ms	1784 KB	Output is correct

Subtask #6

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	95 ms	2044 KB	Output is correct
2	Correct	96 ms	2044 KB	Output is correct
3	Correct	204 ms	3568 KB	Output is correct
4	Correct	99 ms	2928 KB	Output is correct
5	Correct	60 ms	2036 KB	Output is correct
6	Correct	103 ms	3440 KB	Output is correct
7	Correct	112 ms	3436 KB	Output is correct
8	Correct	82 ms	2004 KB	Output is correct

Subtask #7

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	0 ms	384 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	0 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	0 ms	384 KB	Output is correct
18	Correct	0 ms	384 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	1 ms	384 KB	Output is correct
21	Correct	1 ms	384 KB	Output is correct
22	Correct	1 ms	384 KB	Output is correct
23	Correct	1 ms	384 KB	Output is correct
24	Correct	1 ms	384 KB	Output is correct
25	Correct	1 ms	384 KB	Output is correct
26	Correct	1 ms	384 KB	Output is correct
27	Correct	225 ms	3568 KB	Output is correct
28	Correct	225 ms	3568 KB	Output is correct
29	Correct	227 ms	3564 KB	Output is correct
30	Correct	233 ms	3552 KB	Output is correct
31	Correct	109 ms	2800 KB	Output is correct
32	Correct	51 ms	1280 KB	Output is correct
33	Correct	50 ms	1792 KB	Output is correct
34	Correct	51 ms	1792 KB	Output is correct
35	Correct	25 ms	1400 KB	Output is correct
36	Correct	0 ms	384 KB	Output is correct
37	Correct	26 ms	1408 KB	Output is correct
38	Correct	42 ms	1784 KB	Output is correct
39	Correct	95 ms	2044 KB	Output is correct
40	Correct	96 ms	2044 KB	Output is correct
41	Correct	204 ms	3568 KB	Output is correct
42	Correct	99 ms	2928 KB	Output is correct
43	Correct	60 ms	2036 KB	Output is correct
44	Correct	103 ms	3440 KB	Output is correct
45	Correct	112 ms	3436 KB	Output is correct
46	Correct	82 ms	2004 KB	Output is correct
47	Correct	106 ms	3060 KB	Output is correct
48	Correct	106 ms	3068 KB	Output is correct
49	Correct	223 ms	5484 KB	Output is correct
50	Correct	99 ms	3948 KB	Output is correct
51	Correct	101 ms	3436 KB	Output is correct
52	Correct	141 ms	4848 KB	Output is correct
53	Correct	110 ms	4856 KB	Output is correct
54	Correct	112 ms	5612 KB	Output is correct
55	Correct	186 ms	5616 KB	Output is correct