답안 #70887 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70887	2018-08-23T15:35:45 Z	georgerapeanu	Global Warming (CEOI18_glo)	C++11	100 / 100	395 ms	18932 KB

#include <iostream>
#include <vector>
 
using namespace std;
 
const int NMAX = 2e5;
 
int n,x;
int V[NMAX + 5];
 
vector<int> L_PREF[NMAX + 5];
int len_pref;
vector<int> L_SUFF[NMAX + 5];
int len_suff;
int ans = 0;
int dp_pref[NMAX + 5];
 
int main() {
    cin >> n >> x;
 
    for(int i = 1;i <= n;i++){
       cin >> V[i];
    }
 
   V[0] = -(1 << 30);
   V[n + 1] = 1 << 30;
 
    L_PREF[0].push_back(0);
    len_pref = 0;
 
    for(int i = 1;i <= n;i++){
       int st = 0,dr = len_pref + 1;
       while(dr - st > 1){
          int mid = (st + dr) / 2;
          if(V[L_PREF[mid].back()] < V[i]){
             st = mid;
          }
          else{
             dr = mid;
          }
       }
 
       dp_pref[i] = st + 1;
 
       if(st == len_pref){
          len_pref++;
          L_PREF[len_pref].push_back(i);
       }
       else{
          L_PREF[st + 1].push_back(i);
       }
    }
 
    ans = len_pref;
 
    L_SUFF[0].push_back(n + 1);
    len_suff = 0;
 
   for(int i = n;i;i--){
       int st = 0,dr = len_suff + 1;
       while(dr - st > 1){
          int mid = (st + dr) / 2;
          if(V[L_SUFF[mid].back()] > V[i]){
             st = mid;
          }
          else{
             dr = mid;
          }
       }
       if(st == len_suff){
          len_suff++;
          L_SUFF[len_suff].push_back(i);
       }
       else{
          L_SUFF[st + 1].push_back(i);
       }
 
       L_PREF[dp_pref[i]].pop_back();
       while(L_PREF[len_pref].empty()){
          len_pref--;
       }
 
       int st2 = 0,dr2 = len_pref + 1;
       while(dr2 - st2 > 1){
          int mid = (st2 + dr2) / 2;
          if(V[L_PREF[mid].back()] < V[i] + x){
             st2 = mid;
          }
          else{
             dr2 = mid;
          }
       }
       ans = max(ans,st2 + st + 1);
    }
 
    cout << ans;
 
    return 0;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	9720 KB	Output is correct
2	Correct	12 ms	9828 KB	Output is correct
3	Correct	14 ms	9880 KB	Output is correct
4	Correct	12 ms	9880 KB	Output is correct
5	Correct	11 ms	9880 KB	Output is correct
6	Correct	12 ms	9904 KB	Output is correct
7	Correct	10 ms	9936 KB	Output is correct
8	Correct	10 ms	9964 KB	Output is correct
9	Correct	12 ms	9980 KB	Output is correct
10	Correct	12 ms	9980 KB	Output is correct
11	Correct	11 ms	9984 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	9720 KB	Output is correct
2	Correct	12 ms	9828 KB	Output is correct
3	Correct	14 ms	9880 KB	Output is correct
4	Correct	12 ms	9880 KB	Output is correct
5	Correct	11 ms	9880 KB	Output is correct
6	Correct	12 ms	9904 KB	Output is correct
7	Correct	10 ms	9936 KB	Output is correct
8	Correct	10 ms	9964 KB	Output is correct
9	Correct	12 ms	9980 KB	Output is correct
10	Correct	12 ms	9980 KB	Output is correct
11	Correct	11 ms	9984 KB	Output is correct
12	Correct	14 ms	9984 KB	Output is correct
13	Correct	12 ms	9984 KB	Output is correct
14	Correct	12 ms	9984 KB	Output is correct
15	Correct	11 ms	10088 KB	Output is correct
16	Correct	14 ms	10088 KB	Output is correct
17	Correct	11 ms	10092 KB	Output is correct
18	Correct	11 ms	10092 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	9720 KB	Output is correct
2	Correct	12 ms	9828 KB	Output is correct
3	Correct	14 ms	9880 KB	Output is correct
4	Correct	12 ms	9880 KB	Output is correct
5	Correct	11 ms	9880 KB	Output is correct
6	Correct	12 ms	9904 KB	Output is correct
7	Correct	10 ms	9936 KB	Output is correct
8	Correct	10 ms	9964 KB	Output is correct
9	Correct	12 ms	9980 KB	Output is correct
10	Correct	12 ms	9980 KB	Output is correct
11	Correct	11 ms	9984 KB	Output is correct
12	Correct	14 ms	9984 KB	Output is correct
13	Correct	12 ms	9984 KB	Output is correct
14	Correct	12 ms	9984 KB	Output is correct
15	Correct	11 ms	10088 KB	Output is correct
16	Correct	14 ms	10088 KB	Output is correct
17	Correct	11 ms	10092 KB	Output is correct
18	Correct	11 ms	10092 KB	Output is correct
19	Correct	11 ms	10092 KB	Output is correct
20	Correct	12 ms	10092 KB	Output is correct
21	Correct	12 ms	10092 KB	Output is correct
22	Correct	12 ms	10092 KB	Output is correct
23	Correct	11 ms	10092 KB	Output is correct
24	Correct	10 ms	10092 KB	Output is correct
25	Correct	11 ms	10092 KB	Output is correct
26	Correct	14 ms	10092 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	183 ms	13948 KB	Output is correct
2	Correct	212 ms	14076 KB	Output is correct
3	Correct	234 ms	14076 KB	Output is correct
4	Correct	202 ms	14076 KB	Output is correct
5	Correct	346 ms	18156 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	18156 KB	Output is correct
2	Correct	71 ms	18156 KB	Output is correct
3	Correct	63 ms	18156 KB	Output is correct
4	Correct	73 ms	18156 KB	Output is correct
5	Correct	11 ms	18156 KB	Output is correct
6	Correct	82 ms	18156 KB	Output is correct
7	Correct	59 ms	18156 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	124 ms	18156 KB	Output is correct
2	Correct	96 ms	18156 KB	Output is correct
3	Correct	238 ms	18156 KB	Output is correct
4	Correct	339 ms	18264 KB	Output is correct
5	Correct	135 ms	18264 KB	Output is correct
6	Correct	264 ms	18264 KB	Output is correct
7	Correct	304 ms	18604 KB	Output is correct
8	Correct	106 ms	18604 KB	Output is correct

Subtask #7
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	9720 KB	Output is correct
2	Correct	12 ms	9828 KB	Output is correct
3	Correct	14 ms	9880 KB	Output is correct
4	Correct	12 ms	9880 KB	Output is correct
5	Correct	11 ms	9880 KB	Output is correct
6	Correct	12 ms	9904 KB	Output is correct
7	Correct	10 ms	9936 KB	Output is correct
8	Correct	10 ms	9964 KB	Output is correct
9	Correct	12 ms	9980 KB	Output is correct
10	Correct	12 ms	9980 KB	Output is correct
11	Correct	11 ms	9984 KB	Output is correct
12	Correct	14 ms	9984 KB	Output is correct
13	Correct	12 ms	9984 KB	Output is correct
14	Correct	12 ms	9984 KB	Output is correct
15	Correct	11 ms	10088 KB	Output is correct
16	Correct	14 ms	10088 KB	Output is correct
17	Correct	11 ms	10092 KB	Output is correct
18	Correct	11 ms	10092 KB	Output is correct
19	Correct	11 ms	10092 KB	Output is correct
20	Correct	12 ms	10092 KB	Output is correct
21	Correct	12 ms	10092 KB	Output is correct
22	Correct	12 ms	10092 KB	Output is correct
23	Correct	11 ms	10092 KB	Output is correct
24	Correct	10 ms	10092 KB	Output is correct
25	Correct	11 ms	10092 KB	Output is correct
26	Correct	14 ms	10092 KB	Output is correct
27	Correct	183 ms	13948 KB	Output is correct
28	Correct	212 ms	14076 KB	Output is correct
29	Correct	234 ms	14076 KB	Output is correct
30	Correct	202 ms	14076 KB	Output is correct
31	Correct	346 ms	18156 KB	Output is correct
32	Correct	54 ms	18156 KB	Output is correct
33	Correct	71 ms	18156 KB	Output is correct
34	Correct	63 ms	18156 KB	Output is correct
35	Correct	73 ms	18156 KB	Output is correct
36	Correct	11 ms	18156 KB	Output is correct
37	Correct	82 ms	18156 KB	Output is correct
38	Correct	59 ms	18156 KB	Output is correct
39	Correct	124 ms	18156 KB	Output is correct
40	Correct	96 ms	18156 KB	Output is correct
41	Correct	238 ms	18156 KB	Output is correct
42	Correct	339 ms	18264 KB	Output is correct
43	Correct	135 ms	18264 KB	Output is correct
44	Correct	264 ms	18264 KB	Output is correct
45	Correct	304 ms	18604 KB	Output is correct
46	Correct	106 ms	18604 KB	Output is correct
47	Correct	92 ms	18604 KB	Output is correct
48	Correct	123 ms	18604 KB	Output is correct
49	Correct	213 ms	18604 KB	Output is correct
50	Correct	395 ms	18604 KB	Output is correct
51	Correct	218 ms	18604 KB	Output is correct
52	Correct	316 ms	18604 KB	Output is correct
53	Correct	273 ms	18608 KB	Output is correct
54	Correct	264 ms	18932 KB	Output is correct
55	Correct	178 ms	18932 KB	Output is correct

답안 #70887

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