Submission #1088112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088112		Bui_Quoc_Cuong	Global Warming (CEOI18_glo)	C++14	100 / 100	304 ms	29860 KiB

glo

// 29 . 03 . 2008 
#include <bits/stdc++.h>
using namespace std ;
//#define int long long
typedef long long ll ;
typedef vector<int> vi ;
typedef vector<pair<int,int>> vii ;
typedef pair<int,int> ii ;
#define FOR(i,a,b) for(int i(a) ; i <= (int)b ; i++)
#define FORD(i,a,b) for(int i(a) ; i >= (int)b ; i--)
#define FORN(i,a,b) for(int i(a) ; i < (int)b ; i++)
#define all(a) a.begin() , a.end()
#define pb push_back
#define fi first
#define se second
#define BIT(mask,i) ((mask>>i)&1)
#define builtin_popcount builtin_popcountll
#define MASK(a) (1ll << a) 

template<class T> bool maxi(T &x,T y) { if (x < y) { x = y ; return true ;} return false ;}
template<class T> bool mini(T &x,T y) { if (x > y) { x = y ; return true ;} return false ;}

const int MAXN = 2e5 + 5 ;

int n , x ;
ll a[MAXN] ;
int L[MAXN] , VAL , R[MAXN] ;
unordered_map<int,int> pos ; 

void init() {
	cin >> n >> x ; 
	FOR(i,1,n) cin >> a[i] ; 
}

void Compress() {
	vi V ; 
	FOR(i,1,n) V.pb(a[i]) , V.pb(a[i] + x) ; 
	sort(all(V)) ; 
	V.resize(unique(all(V))-V.begin()) ; 
	FOR(i,0,V.size()-1) pos[V[i]] = i + 1 ; 
	VAL = V.size() ; 
}

struct SegmentTree {
	int st[8*MAXN] ; 

	void up(int pos,int val) {
		int id = 1 , l = 1 , r = VAL ; 
		while(l < r) {
			int mid = (l+r)>>1 ; 
			if(pos <= mid) id = id << 1 , r = mid ;
			else id = id << 1 | 1 , l = mid + 1 ; 
		}
		maxi(st[id],val) ; 
		while(id > 1) {
			id>>= 1 ; 
			st[id] = max(st[id<<1],st[id<<1|1]) ; 
		}
	}

	int get(int id,int l,int r,int u,int v) {
		if(l > v || r < u) return 0 ; 
		if(l >= u  && r <= v) return st[id] ; 
		int mid = (l+r)>>1 ; 
		return max(get(id<<1,l,mid,u,v),get(id<<1|1,mid+1,r,u,v)) ; 
	}

	void reset() {
		memset(st,0,sizeof st) ;  
	}
} st ; 

void solve() {
	Compress() ;
	int ans = 0 ;  
	FOR(i,1,n) {
		L[i] = st.get(1,1,VAL,1,pos[a[i]+x]-1) + 1 ; 
		int val = st.get(1,1,VAL,1,pos[a[i]]-1) + 1 ; 
		st.up(pos[a[i]],val) ;
		maxi(ans,val) ; 
		maxi(ans,L[i]) ;
	}
	st.reset() ;
	FORD(i,n,1) {
		R[i] = st.get(1,1,VAL,pos[a[i]+x]+1,VAL) + 1 ; 
		st.up(pos[a[i]+x],R[i]) ; 
	}	
	FOR(i,1,n) maxi(ans,L[i]+R[i]-1) ;
	cout << ans ; 
}

signed main() {
    #define task ""
    ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ; 
    if(fopen(task".inp","r")) {
        freopen(task".inp","r",stdin) ; freopen(task".out","w",stdout) ; 
    }
    init() ;
    solve() ;
    cerr << "TIME : " << clock() * 0.001 << "s" << endl ;
    return 0 ; 
}
/* Watbor */ 

Compilation message (stderr)

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

• 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