답안 #679814

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
679814	2023-01-09T10:06:04 Z	peijar	Global Warming (CEOI18_glo)	C++17	100 / 100	126 ms	13216 KB

#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

vector<int> calcLIS(vector<int> vec) {
  vector<int> curLis;
  int n = vec.size();
  vector<int> ret(n);
  for (int i = 0; i < n; ++i) {
    int pos =
        lower_bound(curLis.begin(), curLis.end(), vec[i]) - curLis.begin();
    ret[i] = pos + 1;
    if (pos == (int)curLis.size())
      curLis.push_back(vec[i]);
    else
      curLis[pos] = vec[i];
  }
  return ret;
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int n, x;
  cin >> n >> x;

  vector<int> vec(n);
  for (int &y : vec)
    cin >> y;

  vector<int> lisStart, lisEnd;

  lisEnd = calcLIS(vec);
  {
    vector<int> vec2 = vec;
    reverse(vec2.begin(), vec2.end());
    for (int &y : vec2)
      y *= -1;
    lisStart = calcLIS(vec2);
    reverse(lisStart.begin(), lisStart.end());
  }

  dbg(lisStart, lisEnd);

  set<pair<int, int>> curChoices;
  int sol = 0;
  for (int i = 0; i < n; ++i) {
    sol = max(sol, lisStart[i]);
    auto it = curChoices.lower_bound({vec[i] + x, 0LL});
    if (it != curChoices.begin()) {
      --it;
      sol = max(sol, it->second + lisStart[i]);
    }
    while ((it = curChoices.lower_bound({vec[i], 0LL})) != curChoices.end()) {
      if (it->second <= lisEnd[i])
        curChoices.erase(it);
      else
        break;
    }
    it = curChoices.lower_bound({vec[i], 0LL});
    if (it == curChoices.end() or it->first > vec[i])
      curChoices.emplace(vec[i], lisEnd[i]);
  }
  cout << sol << endl;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
13.0 / 13.0

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

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	108 ms	8160 KB	Output is correct
2	Correct	115 ms	10088 KB	Output is correct
3	Correct	116 ms	10160 KB	Output is correct
4	Correct	109 ms	10164 KB	Output is correct
5	Correct	102 ms	12312 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	2264 KB	Output is correct
2	Correct	25 ms	2736 KB	Output is correct
3	Correct	25 ms	2748 KB	Output is correct
4	Correct	21 ms	3336 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	30 ms	3292 KB	Output is correct
7	Correct	20 ms	2788 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	47 ms	4252 KB	Output is correct
2	Correct	47 ms	5208 KB	Output is correct
3	Correct	94 ms	9992 KB	Output is correct
4	Correct	108 ms	12396 KB	Output is correct
5	Correct	56 ms	6352 KB	Output is correct
6	Correct	97 ms	11924 KB	Output is correct
7	Correct	81 ms	12560 KB	Output is correct
8	Correct	44 ms	5180 KB	Output is correct

Subtask #7
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	320 KB	Output is correct
5	Correct	0 ms	320 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	316 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	324 KB	Output is correct
15	Correct	1 ms	316 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	328 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	108 ms	8160 KB	Output is correct
28	Correct	115 ms	10088 KB	Output is correct
29	Correct	116 ms	10160 KB	Output is correct
30	Correct	109 ms	10164 KB	Output is correct
31	Correct	102 ms	12312 KB	Output is correct
32	Correct	24 ms	2264 KB	Output is correct
33	Correct	25 ms	2736 KB	Output is correct
34	Correct	25 ms	2748 KB	Output is correct
35	Correct	21 ms	3336 KB	Output is correct
36	Correct	1 ms	212 KB	Output is correct
37	Correct	30 ms	3292 KB	Output is correct
38	Correct	20 ms	2788 KB	Output is correct
39	Correct	47 ms	4252 KB	Output is correct
40	Correct	47 ms	5208 KB	Output is correct
41	Correct	94 ms	9992 KB	Output is correct
42	Correct	108 ms	12396 KB	Output is correct
43	Correct	56 ms	6352 KB	Output is correct
44	Correct	97 ms	11924 KB	Output is correct
45	Correct	81 ms	12560 KB	Output is correct
46	Correct	44 ms	5180 KB	Output is correct
47	Correct	59 ms	5180 KB	Output is correct
48	Correct	51 ms	5124 KB	Output is correct
49	Correct	112 ms	10092 KB	Output is correct
50	Correct	104 ms	12404 KB	Output is correct
51	Correct	106 ms	10904 KB	Output is correct
52	Correct	126 ms	12548 KB	Output is correct
53	Correct	120 ms	12500 KB	Output is correct
54	Correct	79 ms	13216 KB	Output is correct
55	Correct	85 ms	10120 KB	Output is correct

답안 #679814

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