oj.uz

답안 #613868

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
613868 2022-07-30T12:15:00 Z Vladth11 Global Warming (CEOI18_glo) C++14
100 / 100
 1487 ms 111356 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 200001;
const ll VMAX = 2000000001;
const ll INF = (1LL << 60);
const ll MOD = 998244353;
const ll BLOCK = 447;
const ll base = 117;
const ll nr_of_bits = 21;

int n, x;
int v[NMAX];
unordered_map <int, int> aib;
int lis[NMAX];
int acum[NMAX];
int maxim = 0;
int lds[NMAX];

int query(int x){
    int maxim = 0;
    for(; x > 0; x -= x&(-x))
        maxim = max(maxim, aib[x]);
    return maxim;
}

void update(ll node, int x){
    assert(node != 0);
    for(; node < VMAX; node += node&(-node))
        aib[node] = max(aib[node], x);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i;
    cin >> n >> x;
    for(i = 1; i <= n; i++){
        cin >> v[i];
        int r = 0, pas = (1 << nr_of_bits);
        while(pas){
            if(r + pas <= maxim && lis[r + pas] <= v[i])
                r += pas;
            pas /= 2;
        }
        if(lis[r] != v[i])
        r++;
        lis[r] = v[i];
        acum[i] = r;
        maxim = max(maxim, r);
    }
    for(i = 0; i <= maxim; i++){
        lis[i] = 0;
    }
    maxim = 0;
    for(i = n; i >= 1; i--){
        int r = 0, pas = (1 << nr_of_bits);
        while(pas){
            if(r + pas <= maxim && lis[r + pas] >= v[i])
                r += pas;
            pas /= 2;
        }
        if(lis[r] != v[i])
        r++;
        lis[r] = v[i];
        maxim = max(maxim, r);
        lds[i] = r;
    }
    maxim = 0;
    for(i = 1; i <= n; i++){
        maxim = max(maxim, lds[i] + query(v[i] + x - 1));
        update(v[i], acum[i]);
    }
    cout << maxim;
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 3 ms 1108 KB Output is correct
20 Correct 5 ms 1108 KB Output is correct
21 Correct 5 ms 1108 KB Output is correct
22 Correct 4 ms 1108 KB Output is correct
23 Correct 3 ms 724 KB Output is correct
24 Correct 2 ms 724 KB Output is correct
25 Correct 2 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 1370 ms 103412 KB Output is correct
2 Correct 1398 ms 105064 KB Output is correct
3 Correct 1421 ms 105060 KB Output is correct
4 Correct 1381 ms 105132 KB Output is correct
5 Correct 609 ms 57440 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 262 ms 27708 KB Output is correct
2 Correct 256 ms 27836 KB Output is correct
3 Correct 308 ms 27836 KB Output is correct
4 Correct 152 ms 20516 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 39 ms 2380 KB Output is correct
7 Correct 189 ms 21452 KB Output is correct

Subtask #6
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 742 ms 58056 KB Output is correct
2 Correct 723 ms 58704 KB Output is correct
3 Correct 1487 ms 111356 KB Output is correct
4 Correct 691 ms 60476 KB Output is correct
5 Correct 105 ms 11792 KB Output is correct
6 Correct 186 ms 23444 KB Output is correct
7 Correct 170 ms 24036 KB Output is correct
8 Correct 528 ms 45864 KB Output is correct

Subtask #7
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 3 ms 1108 KB Output is correct
20 Correct 5 ms 1108 KB Output is correct
21 Correct 5 ms 1108 KB Output is correct
22 Correct 4 ms 1108 KB Output is correct
23 Correct 3 ms 724 KB Output is correct
24 Correct 2 ms 724 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1370 ms 103412 KB Output is correct
28 Correct 1398 ms 105064 KB Output is correct
29 Correct 1421 ms 105060 KB Output is correct
30 Correct 1381 ms 105132 KB Output is correct
31 Correct 609 ms 57440 KB Output is correct
32 Correct 262 ms 27708 KB Output is correct
33 Correct 256 ms 27836 KB Output is correct
34 Correct 308 ms 27836 KB Output is correct
35 Correct 152 ms 20516 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 39 ms 2380 KB Output is correct
38 Correct 189 ms 21452 KB Output is correct
39 Correct 742 ms 58056 KB Output is correct
40 Correct 723 ms 58704 KB Output is correct
41 Correct 1487 ms 111356 KB Output is correct
42 Correct 691 ms 60476 KB Output is correct
43 Correct 105 ms 11792 KB Output is correct
44 Correct 186 ms 23444 KB Output is correct
45 Correct 170 ms 24036 KB Output is correct
46 Correct 528 ms 45864 KB Output is correct
47 Correct 629 ms 52624 KB Output is correct
48 Correct 665 ms 53516 KB Output is correct
49 Correct 1347 ms 104892 KB Output is correct
50 Correct 626 ms 55232 KB Output is correct
51 Correct 118 ms 9392 KB Output is correct
52 Correct 151 ms 13832 KB Output is correct
53 Correct 198 ms 23628 KB Output is correct
54 Correct 186 ms 24288 KB Output is correct
55 Correct 945 ms 84264 KB Output is correct