Submission #491297

#	Time	Username	Problem	Language	Result	Execution time	Memory
491297		tphuc2908	Global Warming (CEOI18_glo)	C++14	100 / 100	299 ms	17280 KiB

glo

#include<bits/stdc++.h>

using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define repi(i,x,y) for(int i = x; i >= y; --i)
#define ci(x) int x; cin>> x
#define TC(t) ci(t); while(t--)
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define cii(x, y) ci(x); ci(y)
#define ciii(x, y, z) ci(x); ci(y); ci(z)
#define mp make_pair
//#define int long long
typedef long long ll;
typedef vector<int> vi;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int mod1 = 1e9 + 9;
const int pi = 31, pii = 29, piii = 41;
const int inf = 2e9 + 5;
const int block = 330;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

void readfile(){
    #ifdef ONLINE_JUDGE
    #else
        freopen("text.inp", "r", stdin);
    #endif // ONLINE_JUDGE
//    freopen("cowjog.in", "r", stdin);
//    freopen("cowjog.out", "w", stdout);
}

/*
    consider this subsequence
    a1 < a2 < ... < ai > ai+1 < ai+2 ... < aj
    either increase ai+1->aj or decrease a1->ai by x
    call s[i] is max lis starting with i
    call e[i] is max lis ending with i
*/

int n, x;
int a[N], s[N], e[N];
vector<int> b;
unordered_map<int,int> m;

void inp(){
    cin >> n >> x;
    rep(i,1,n){
        cin >> a[i];
        if(m[a[i]]==0){
            b.pb(a[i]);
            m[a[i]] = 1;
        }
    }
    sort(all(b));
}

struct seg_tree{
    int sz = 1;
    vector<int> val;

    void inp(int n){
        while(sz < n)
            sz <<= 1;
        val.resize(2*sz, 0);
    }

    void update(int x, int lx, int rx, int i, int v){
        if(rx - lx == 1){
            val[x] = max(val[x], v);
            return;
        }
        int mid = (lx + rx) >> 1;
        if(i < mid)
            update(2*x+1,lx,mid,i,v);
        else update(2*x+2,mid,rx,i,v);
        val[x] = max(val[2*x+1], val[2*x+2]);
    }

    void update(int i, int v){
        update(0,0,sz,i,v);
    }

    int get(int x, int lx, int rx, int l, int r){
        if(r <= lx || rx <= l)
            return 0;
        if(l <= lx && rx <= r)
            return val[x];
        int mid = (lx + rx) >> 1;
        int left = get(2*x+1,lx,mid,l,r);
        int right = get(2*x+2,mid,rx,l,r);
        return max(left, right);
    }

    int get(int l, int r){
        return get(0, 0, sz, l, r);
    }
} st;

int dp[N];

void process(){
    fill(dp + 1, dp + n + 1, inf);
    rep(i,1,n){
        int pos = lower_bound(dp + 1, dp + n + 1, a[i]) - dp;
        dp[pos] = a[i];
        e[i] = pos;
    }
    fill(dp + 1, dp + n + 1, -inf);
    repi(i,n,1){
        int l = 1, r = n, pos;
        while(l <= r){
            int mid = (l + r) >> 1;
            if(dp[mid] <= a[i]){
                pos = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        dp[pos] = a[i];
        s[i] = n + 1 - pos;
    }
    st.inp(n);
    int res = 0;
    rep(i,1,n){
        int pos = upper_bound(all(b), a[i] - x) - b.begin();
        int pos1 = lower_bound(all(b), a[i] + x) - b.begin() - 1;
        res = max(res, st.get(pos, pos1 + 1) + s[i]);
        int p = lower_bound(all(b), a[i]) - b.begin();
        st.update(p, e[i]);
    }
    cout << res;
}

int main() {
  //  readfile();
//    TC(t){
        inp();
        process();
//    }
    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'void readfile()':
glo.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen("text.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp: In function 'void process()':
glo.cpp:127:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  127 |         s[i] = n + 1 - pos;
      |                ~~~~~~^~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25