oj.uz

Submission #1088111

# Submission time Handle Problem Language Result Execution time Memory
1088111 2024-09-14T01:33:48 Z Bui_Quoc_Cuong Global Warming (CEOI18_glo) C++14
0 / 100
 321 ms 29760 KB 
// 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() ; 
	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) ;
	}
	st.reset() ;
	FORD(i,n,1) {
		R[i] = st.get(1,1,VAL,pos[a[i]+x],VAL) + 1 ; 
		st.up(pos[a[i]+x],R[i]) ; 
	}	
	int ans = 0 ; 
	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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 20552 KB Output is correct
2 Correct 227 ms 20568 KB Output is correct
3 Correct 231 ms 20572 KB Output is correct
4 Correct 222 ms 20724 KB Output is correct
5 Incorrect 104 ms 15568 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 12328 KB Output is correct
2 Correct 57 ms 12332 KB Output is correct
3 Correct 58 ms 12384 KB Output is correct
4 Incorrect 31 ms 9956 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 18124 KB Output is correct
2 Correct 132 ms 18112 KB Output is correct
3 Correct 321 ms 29760 KB Output is correct
4 Incorrect 139 ms 19804 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -