Submission #960651

#	Time	Username	Problem	Language	Result	Execution time	Memory
960651		HossamHero7	Global Warming (CEOI18_glo)	C++14	28 / 100	2071 ms	26280 KiB

glo

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 2e5 + 5;
int dp[N][2];
struct SegTree{
    vector<int> tree;
    int n;
    SegTree(int _n){
        n = _n;
        tree.resize(4*n+5);
    }
    void update(int node,int l,int r,int idx,int val){
        if(l == r) return tree[node] = max(tree[node] , val) , void();
        int md = l + r >> 1;
        idx <= md ? update(node<<1,l,md,idx,val) : update(node<<1|1,md+1,r,idx,val);
        tree[node] = max(tree[node<<1],tree[node<<1|1]);
    }
    int query(int node,int l,int r,int lQ,int rQ){
        if(l > r || l > rQ || lQ > r) return 0;
        if(lQ <= l && r <= rQ) return tree[node];
        int md = l + r >> 1;
        return max(query(node<<1,l,md,lQ,rQ) , query(node<<1|1,md+1,r,lQ,rQ));
    }
    void update(int idx,int val){
        update(1,1,n,idx,val);
    }
    int query(int l,int r){
        if(l > r) return 0;
        return query(1,1,n,l,r);
    }
};
void compress(vector<int> &a){
    int n = a.size();
    vector<pair<int,int>> b(n);
    for(int i=0;i<n;i++){
        b[i].first = a[i];
        b[i].second = i;
    }
    sort(b.begin(),b.end());
    a[b[0].second] = 1;
    int cnt = 1;
    for(int i=1;i<n;i++){
        if(b[i].first == b[i-1].first){
            a[b[i].second] = a[b[i-1].second];
        }
        else a[b[i].second] = ++cnt;
    }
}
void solve(){
    ll n,x;
    cin>>n>>x;
    vector<ll> v(n);
    for(int i=0;i<n;i++) cin>>v[i];
    vector<int> tmp;
    for(auto i : v) {
        tmp.push_back(i);
        tmp.push_back(i-x+1);
        tmp.push_back(i+1);
    }
    compress(tmp);
    vector<ll> change(n);
    for(int i=0;i<n;i++){
        v[i] = tmp[i*3];
        change[i] = tmp[i*3+1];
    }
    SegTree sg0(3*n+5);
    SegTree sg1(3*n+5);
    for(int i=n-1;i>=0;i--){
        for(int j=0;j<2;j++){
            for(int k=i+1;k<n;k++){
                /*if(v[k] > v[i]){
                    dp[i][j] = max(dp[i][j] , dp[k][j] + 1);
                }*/
                dp[i][j] = j==0?sg0.query(v[i]+1,3*n):sg1.query(v[i]+1,3*n);
            }
            if(!j){
                /*for(int k=i+1;k<n;k++){
                    if(v[k] > v[i]-x){
                        dp[i][j] = max(dp[i][j] , dp[k][1] + 1);
                    }
                }*/
                dp[i][j] = max(dp[i][j] , sg1.query(change[i],3*n));
            }
            j==0?sg0.update(v[i],dp[i][j]+1):sg1.update(v[i],dp[i][j]+1);
        }
    }
    int ans = 0;
    for(int i=0;i<n;i++){
        ans = max(ans, dp[i][0] + 1);
    }
    cout<<ans<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

glo.cpp: In member function 'void SegTree::update(int, int, int, int, int)':
glo.cpp:16:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |         int md = l + r >> 1;
      |                  ~~^~~
glo.cpp: In member function 'int SegTree::query(int, int, int, int, int)':
glo.cpp:23:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |         int md = l + r >> 1;
      |                  ~~^~~

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