답안 #233068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
233068	2020-05-19T06:49:07 Z	AlexLuchianov	Global Warming (CEOI18_glo)	C++14	100 / 100	579 ms	25144 KB

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <map>

using namespace std;
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 200000;
int v[1 + nmax];
map<int,int> mp;

class FenwickTree{
private:
  vector<int> aib;
  int n;
public:
  FenwickTree(int n_){
    n = n_;
    aib.resize(1 + n);
  }
  void update(int pos, int val){
    for(int x = pos; x <= n; x += (x & (x ^ (x - 1))))
      aib[x] = max(aib[x], val);
  }
  int query(int pos){
    int result = 0;
    for(int x = pos; 0 < x; x = (x & (x - 1)))
      result = max(result, aib[x]);
    return result;
  }
};

void normalize(int n, int lim){
  vector<int> temp;
  for(int i = 1; i <= n; i++) {
    temp.push_back(v[i]);
    temp.push_back(v[i] + lim);
  }
  sort(temp.begin(), temp.end());
  temp.erase(unique(temp.begin(), temp.end()), temp.end());
  for(int i = 0; i < temp.size(); i++)
    mp[temp[i]] = 1 + i;
}


int main()
{
  int n, lim;
  cin >> n >> lim;
  for(int i = 1;i <= n; i++)
    cin >> v[i];
  normalize(n, lim);
  FenwickTree basic(1 + 2 * n), advanced(1 + 2 * n);
  for(int i = 1;i <= n; i++){
    int id1 = mp[v[i]];
    int id2 = mp[v[i] + lim];
    advanced.update(id2, max(basic.query(id2 - 1), advanced.query(id2 - 1)) + 1);
    basic.update(id1, basic.query(id1 - 1) + 1);
  }
  cout << advanced.query(2 * n);
  return 0;
}

Compilation message

glo.cpp: In function 'void normalize(int, int)':
glo.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < temp.size(); i++)
                  ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
13.0 / 13.0

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

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	380 ms	15648 KB	Output is correct
2	Correct	362 ms	15688 KB	Output is correct
3	Correct	354 ms	15560 KB	Output is correct
4	Correct	368 ms	15560 KB	Output is correct
5	Correct	163 ms	10056 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	97 ms	6500 KB	Output is correct
2	Correct	94 ms	6504 KB	Output is correct
3	Correct	90 ms	6504 KB	Output is correct
4	Correct	48 ms	3952 KB	Output is correct
5	Correct	5 ms	256 KB	Output is correct
6	Correct	48 ms	3944 KB	Output is correct
7	Correct	77 ms	5864 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	235 ms	12636 KB	Output is correct
2	Correct	237 ms	12632 KB	Output is correct
3	Correct	579 ms	25032 KB	Output is correct
4	Correct	219 ms	14792 KB	Output is correct
5	Correct	139 ms	12280 KB	Output is correct
6	Correct	245 ms	23060 KB	Output is correct
7	Correct	282 ms	23700 KB	Output is correct
8	Correct	179 ms	12764 KB	Output is correct

Subtask #7
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	256 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	4 ms	256 KB	Output is correct
6	Correct	5 ms	256 KB	Output is correct
7	Correct	4 ms	384 KB	Output is correct
8	Correct	4 ms	256 KB	Output is correct
9	Correct	4 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	4 ms	384 KB	Output is correct
12	Correct	5 ms	256 KB	Output is correct
13	Correct	5 ms	256 KB	Output is correct
14	Correct	5 ms	256 KB	Output is correct
15	Correct	5 ms	384 KB	Output is correct
16	Correct	4 ms	384 KB	Output is correct
17	Correct	4 ms	384 KB	Output is correct
18	Correct	5 ms	384 KB	Output is correct
19	Correct	6 ms	384 KB	Output is correct
20	Correct	6 ms	512 KB	Output is correct
21	Correct	6 ms	384 KB	Output is correct
22	Correct	6 ms	384 KB	Output is correct
23	Correct	5 ms	384 KB	Output is correct
24	Correct	5 ms	384 KB	Output is correct
25	Correct	5 ms	384 KB	Output is correct
26	Correct	5 ms	384 KB	Output is correct
27	Correct	380 ms	15648 KB	Output is correct
28	Correct	362 ms	15688 KB	Output is correct
29	Correct	354 ms	15560 KB	Output is correct
30	Correct	368 ms	15560 KB	Output is correct
31	Correct	163 ms	10056 KB	Output is correct
32	Correct	97 ms	6500 KB	Output is correct
33	Correct	94 ms	6504 KB	Output is correct
34	Correct	90 ms	6504 KB	Output is correct
35	Correct	48 ms	3952 KB	Output is correct
36	Correct	5 ms	256 KB	Output is correct
37	Correct	48 ms	3944 KB	Output is correct
38	Correct	77 ms	5864 KB	Output is correct
39	Correct	235 ms	12636 KB	Output is correct
40	Correct	237 ms	12632 KB	Output is correct
41	Correct	579 ms	25032 KB	Output is correct
42	Correct	219 ms	14792 KB	Output is correct
43	Correct	139 ms	12280 KB	Output is correct
44	Correct	245 ms	23060 KB	Output is correct
45	Correct	282 ms	23700 KB	Output is correct
46	Correct	179 ms	12764 KB	Output is correct
47	Correct	205 ms	12636 KB	Output is correct
48	Correct	210 ms	12632 KB	Output is correct
49	Correct	521 ms	24904 KB	Output is correct
50	Correct	195 ms	14792 KB	Output is correct
51	Correct	154 ms	11328 KB	Output is correct
52	Correct	211 ms	15032 KB	Output is correct
53	Correct	262 ms	24504 KB	Output is correct
54	Correct	299 ms	25144 KB	Output is correct
55	Correct	356 ms	21960 KB	Output is correct

답안 #233068

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