oj.uz

답안 #972962

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972962 2024-05-01T10:55:42 Z efedmrlr Global Warming (CEOI18_glo) C++17
75 / 100
 545 ms 262144 KB 
#include <bits/stdc++.h>

#define lli long long int
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define ld long double

using namespace std;

const int N = 1e5 + 5;
const int INF = 1e9 + 500;
const int MX = 1e9 + 5;
void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

struct Node {
    
    Node *lc, *rc;
    int val;
    Node() : lc(NULL), rc(NULL), val(0) {}
    void extend() {
        if(!lc) lc = new Node();
        if(!rc) rc = new Node();
    }
    int query(int tl, int tr, int l, int r) {
        if(tl >= l && tr <= r) {
            return val;
        }
        if(tl > r || tr < l) return 0;
        int tm = (tl + tr) >> 1;
        extend();
        return max(lc->query(tl, tm, l, r), rc->query(tm + 1, tr, l, r));
    }
    void update(int tl, int tr, int ind, int nw) {
        if(tl == tr) {
            val = max(val, nw);
            return;
        }
        int tm = (tl + tr) >> 1;
        extend();
        if(ind <= tm) {
            lc->update(tl, tm, ind, nw);
        }
        else {
            rc->update(tm + 1, tr, ind, nw);
        }
        val = max(lc->val, rc->val);
    }
};


int n, x;
vector<int> t;
vector<int> pr, suf;
Node *seg;

void solve() {
    cin >> n >> x;
    t.assign(n + 1, 0);
    pr.resize(n + 3);
    suf.resize(n + 3);
    for(int i = 1; i <= n; i++) {
        cin >> t[i];
    }
    set<array<int, 2> > st;
    for(int i = 1; i <= n; i++) {
        auto itr = st.lower_bound({t[i], 0});
        if(itr == st.end()) {
            pr[i] = st.size() + 1;
        }
        else {
            pr[i] = (*itr)[1];
            st.erase(itr);
        }
        st.insert({t[i], pr[i]});
    }
    st.clear();
    for(int i = n; i >= 1; i--) {
        auto itr = st.lower_bound({-t[i], 0});
        if(itr == st.end()) {
            suf[i] = st.size() + 1;
        }
        else {
            suf[i] = (*itr)[1];
            st.erase(itr);
        }
        st.insert({-t[i], suf[i]});
    }
    st.clear();
    seg = new Node();
    int ans = 0;
    for(int i = n; i >= 1; i--) {
        int ret = pr[i];
        if(t[i] + 1 - x <= MX) {
            ret += seg->query(0, MX, max(0, t[i] + 1 - x), MX);
        }
        ans = max(ans, ret);
        seg->update(0, MX, t[i], suf[i]);
    }
    cout << ans << "\n";

}

signed main() {
    fastio();
    solve();
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
13.0 / 13.0

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

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 366 ms 158132 KB Output is correct
2 Correct 363 ms 158032 KB Output is correct
3 Correct 375 ms 158000 KB Output is correct
4 Correct 367 ms 158036 KB Output is correct
5 Correct 208 ms 86768 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 53072 KB Output is correct
2 Correct 98 ms 53180 KB Output is correct
3 Correct 96 ms 53072 KB Output is correct
4 Correct 54 ms 28536 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 34 ms 4436 KB Output is correct
7 Correct 68 ms 37200 KB Output is correct

Subtask #6
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 85584 KB Output is correct
2 Correct 161 ms 85328 KB Output is correct
3 Correct 312 ms 158188 KB Output is correct
4 Correct 176 ms 86608 KB Output is correct
5 Correct 58 ms 8272 KB Output is correct
6 Correct 116 ms 15696 KB Output is correct
7 Correct 104 ms 16208 KB Output is correct
8 Correct 110 ms 60748 KB Output is correct

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 0 ms 456 KB Output is correct
19 Correct 3 ms 2652 KB Output is correct
20 Correct 3 ms 2396 KB Output is correct
21 Correct 3 ms 2260 KB Output is correct
22 Correct 2 ms 1628 KB Output is correct
23 Correct 2 ms 1116 KB Output is correct
24 Correct 2 ms 1372 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 366 ms 158132 KB Output is correct
28 Correct 363 ms 158032 KB Output is correct
29 Correct 375 ms 158000 KB Output is correct
30 Correct 367 ms 158036 KB Output is correct
31 Correct 208 ms 86768 KB Output is correct
32 Correct 94 ms 53072 KB Output is correct
33 Correct 98 ms 53180 KB Output is correct
34 Correct 96 ms 53072 KB Output is correct
35 Correct 54 ms 28536 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 34 ms 4436 KB Output is correct
38 Correct 68 ms 37200 KB Output is correct
39 Correct 176 ms 85584 KB Output is correct
40 Correct 161 ms 85328 KB Output is correct
41 Correct 312 ms 158188 KB Output is correct
42 Correct 176 ms 86608 KB Output is correct
43 Correct 58 ms 8272 KB Output is correct
44 Correct 116 ms 15696 KB Output is correct
45 Correct 104 ms 16208 KB Output is correct
46 Correct 110 ms 60748 KB Output is correct
47 Correct 229 ms 127312 KB Output is correct
48 Correct 238 ms 144684 KB Output is correct
49 Runtime error 545 ms 262144 KB Execution killed with signal 9
50 Halted 0 ms 0 KB -