제출 #1304095

#제출 시각아이디문제언어결과실행 시간메모리
1304095dex111222333444555Global Warming (CEOI18_glo)C++20
100 / 100
165 ms6828 KiB
#include <bits/stdc++.h>
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ii pair<int, int>
#define fi first
#define se second
#define all(v) begin(v), end(v)
#define siz(v) (int)(v).size()
using namespace std;

const int MAXN = 2e5 + 4, mod = 1e9 + 7, MAXB = 20;

template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}
template<class X, class Y> bool maximize(X &x, const Y &y){return x < y ? x = y, 1: 0;}

void add(int &a, const int &b){
    a += b;
    if (a >= mod) a -= mod;
}

void sub(int &a, const int &b){
    a -= b;
    if (a < 0) a += mod;
}

int mul(const int &a, const int &b){
    return 1LL * a * 1LL * b % mod;
}

int numVal, maxDelta, val[MAXN], pre[MAXN], suff[MAXN];
vector<int> compress;

struct fenwickTree{
    int n;
    vector<int> bit;

    fenwickTree(int _n = 0): n(_n){
        bit.assign(n + 1, 0);
    }

    void update(int pos, const int &val, bool inc){
        if (!inc){
            for(; pos <= n; pos += pos & -pos) maximize(bit[pos], val);
        }else{
            for(; pos > 0; pos ^= pos & -pos) maximize(bit[pos], val);
        }
    }

    int get(int pos, bool inc){
        int best = 0;
        if (!inc){
            for(; pos > 0; pos ^= pos & -pos) maximize(best, bit[pos]);
        }else{
            for(; pos <= n; pos += pos & -pos) maximize(best, bit[pos]);
        }
        return best;
    }
};

int getPos(const int &pos){
    return lower_bound(all(compress), pos) - begin(compress) + 1;
}

void input(){
    cin >> numVal >> maxDelta;
    for(int i = 1; i <= numVal; i++) cin >> val[i];
}

void solve(){
    for(int i = 1; i <= numVal; i++){
        compress.push_back(val[i]);
        compress.push_back(val[i] - maxDelta);
    }

    sort(all(compress)); compress.resize(unique(all(compress)) - begin(compress));

    fenwickTree myBit(siz(compress));
    for(int i = 1; i <= numVal; i++){
        pre[i] = myBit.get(getPos(val[i] - maxDelta) - 1, 0) + 1;
        myBit.update(getPos(val[i] - maxDelta), pre[i], 0);
    }


    int res = 0;
    myBit = fenwickTree(siz(compress));
    for(int i = numVal; i >= 1; i--){
        maximize(res, pre[i] + myBit.get(getPos(val[i] - maxDelta) + 1, 1));
        suff[i] = myBit.get(getPos(val[i]) + 1, 1) + 1;
        myBit.update(getPos(val[i]), suff[i], 1);
    }

    cout << res << '\n';

}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    input();
    solve();
}

컴파일 시 표준 에러 (stderr) 메시지

glo.cpp: In function 'int main()':
glo.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...