Submission #1029887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029887		nguyenhainam1012	Global Warming (CEOI18_glo)	C++17	100 / 100	238 ms	22304 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#pragma omp
#pragma simd
#pragma unroll
#pragma pack
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC target("avx","sse2")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#define int long long
#define fi first
#define se second
#define pb push_back
#define M_PI 3.14159265358979323846
#define set_on(x, i) ((x) | (1LL << i))
#define set_off(x, i) ((x) & ~(1LL << i))
#define get_bit(x, i) ((x >> i) & 1LL)
#define count_bit(x) __builtin_popcountll(x)
#define rep(i, a, b) for(int i=a; i<b; i++)
const int maxn=1e6+5;
const int mxn=1e7+5;
const int N =4e5+5;
int base=313,basej=431;
ll MOD=790972;//
int mod=1e9+7;
int inf=1e18;
typedef pair<int, int> pii;
const int S = 19;
const int LOG = log2(N)+1;
  ll sqr(ll x) {
      return x*x;
  }
  ll power(ll a, ll b) {
     if (b == 0) return 1 ;
          if (b % 2 == 0)
              return sqr(power(a, b/2)) ;
                  return a * (sqr(power(a, b/2)) ) ;}
int n,x,a[N],bit0[N],bit1[N],bit2[N];
vector<int>b1,b2;
void update(int *bit,int pos,int val){
    for(;pos<N;pos+=pos&(-pos))bit[pos]=max(bit[pos],val);
}
int get(int *bit,int pos){
    int res=0;
    for(;pos>0;pos-=pos&(-pos))res=max(res,bit[pos]);
    return res;
}
void solve(){
    int ans=1;
    for(int i=1;i<=n;i++){
        int nonadd=lower_bound(b1.begin(),b1.end(),a[i])-b1.begin();
        int add=lower_bound(b1.begin(),b1.end(),a[i]+x)-b1.begin();
        int mx1=get(bit0,nonadd-1)+1;
        int mx2=max(get(bit0,add-1),get(bit1,add-1))+1;
        ans=max({ans,mx1,mx2});
        update(bit0,nonadd,mx1);
        update(bit1,add,mx2);
    }
    for(int i=1;i<N;i++)bit1[i]=bit0[i]=bit2[i]=0;
    for(int i=1;i<=n;i++){
        int nonadd=lower_bound(b2.begin(),b2.end(),a[i])-b2.begin();
        int add=lower_bound(b2.begin(),b2.end(),a[i]+x)-b2.begin();
        int mx1=get(bit0,nonadd-1)+1;
        int mx2=max(get(bit0,add-1),get(bit1,add-1))+1;
        ans=max({ans,mx1,mx2});
        update(bit0,nonadd,mx1);
        update(bit1,add,mx2);
    }
    cout << ans;
}
void input(){
    cin >> n >> x; \
    b1.pb(-inf); b2.pb(-inf);
    for(int i=1;i<=n;i++){
            cin >> a[i] ; b1.pb(a[i]);b2.pb(a[i]);
            b1.pb(a[i]+x);b2.pb(a[i]-x);
    }
    sort(b1.begin(),b1.end()); b1.erase(unique(b1.begin(),b1.end()),b1.end());
    sort(b2.begin(),b2.end()); b2.erase(unique(b2.begin(),b2.end()),b2.end());
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
//  	if (fopen("LROP.inp", "r")) {
//  		freopen("LROP.inp", "r", stdin);
//  		freopen("LROP.out", "wN", stdout);
//  	}

    int t;t=1;
    while(t--){
        input();
        solve();
    }
}

Compilation message (stderr)

glo.cpp:4: warning: ignoring '#pragma omp ' [-Wunknown-pragmas]
    4 | #pragma omp
      | 
glo.cpp:5: warning: ignoring '#pragma simd ' [-Wunknown-pragmas]
    5 | #pragma simd
      | 
glo.cpp:6: warning: ignoring '#pragma unroll ' [-Wunknown-pragmas]
    6 | #pragma unroll
      | 
glo.cpp:7:9: warning: missing '(' after '#pragma pack' - ignored [-Wpragmas]
    7 | #pragma pack
      |         ^~~~

• 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