oj.uz

답안 #972956

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972956 2024-05-01T10:45:50 Z efedmrlr Global Warming (CEOI18_glo) C++17
0 / 100
 412 ms 160452 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.upper_bound({t[i], INF});
        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.upper_bound({-t[i], INF});
        if(itr == st.end()) {
            suf[i] = st.size() + 1;
        }
        else {
            suf[i] = (*itr)[1];
            st.erase(itr);
        }
        st.insert({-t[i], suf[i]});
    }
    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, 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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 370 ms 160452 KB Output is correct
2 Correct 412 ms 160060 KB Output is correct
3 Correct 412 ms 160132 KB Output is correct
4 Correct 396 ms 160084 KB Output is correct
5 Incorrect 254 ms 92528 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 53520 KB Output is correct
2 Correct 106 ms 53844 KB Output is correct
3 Correct 99 ms 53640 KB Output is correct
4 Incorrect 61 ms 30068 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 86608 KB Output is correct
2 Correct 170 ms 86312 KB Output is correct
3 Correct 354 ms 160160 KB Output is correct
4 Incorrect 215 ms 92524 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -