Submission #1286592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286592		Bui_Quoc_Cuong	Bouquet (EGOI24_bouquet)	C++20	100 / 100	74 ms	19672 KiB

Main

/* 29 . 03 . 2008 */ 
#include <bits/stdc++.h>
using namespace std ;

bool watbor = 0 ;

typedef long long ll ;
typedef vector<int> vi ;
typedef vector<pair<int,int>> vii ;
typedef pair<int,int> pii ;
typedef pair<ll,int> pli ;
typedef pair<int,ll> pil ;
typedef pair<ll,ll> pll ;

#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 endl '\n' 
#define BIT(mask,i) ((mask>>i)&1)
#define builtin_popcount builtin_popcountll
#define uni(a) sort(all(a)), a.resize(unique(all(a))-a.begin()) 
#define MASK(a) (1ll << a) 

int gcd(int x, int y) {return __gcd(x, y) ;}
int lg(int x) {return __lg(x) ;}
int lcm(int x, int y) {return x / __gcd(x, y) * y ;}

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 N = 4e5 + 5, M = 5e3 + 5, LG = __lg(N) + 1, base = 311 ;
const int oo = 2e9, sm = 1e9 + 7, mod1 = 1e9 + 7, mod2 = 998244353 ;
const long long inf = 1e18 ;

int n;
int L[N], R[N];

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

namespace subtask_1 {
	bool check() {FOR(i, 1, n) if(R[i] != 0) return 0; return 1;}
	int dp[N] ;

	struct SegmentTree {
		int st[4 * N] ; 

		void up(int pos, int val) {
			int id = 1, l = 1, r = n ;
			while(l < r) {
				int mid = (l + r) >> 1 ; 
				if(pos <= mid) id = id << 1, r = mid ; 
				else id = id << 1 | 1, l = mid + 1 ; 
			}
			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)) ; 
		}
	} st ; 

	void solve() {	
		FOR(i, 1, n) {
			dp[i] = st.get(1, 1, n, 0, max(0, i - L[i] - 1)) + 1 ; 
			st.up(i, dp[i]) ;
		}
		cout << *max_element(dp + 1, dp + 1 + n) ; 
	}
}

namespace subtask_2 {
	bool check() {return n <= 5e3; }
	int dp[N] ;

	void solve() {
		FOR(i, 1, n){
			dp[i] = 1; 
			FOR(j, 1, i - 1){
				if(i > j + R[j] && j < i - L[i]) { 
					maxi(dp[i], dp[j] + 1) ; 
				}
			}
		}
		cout << *max_element(dp + 1, dp + 1 + n) ; 
	}
}

namespace subtask_3 {
	bool check() {
		bool hiendeptrai = 1 ;
		return hiendeptrai ;
	}

	struct SegmentTree {
		int st[4 * N] ; 

		void up(int pos, int val) {
			int id = 1, l = 1, r = n ;
			while(l < r) {
				int mid = (l + r) >> 1 ; 
				if(pos <= mid) id = id << 1, r = mid ; 
				else id = id << 1 | 1, l = mid + 1 ; 
			}
			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)) ; 
		}
	} st ; 

	int dp[N] ;
	vi pos[N] ;

	void solve() {
		FOR(i, 1, n) pos[i + R[i]].push_back(i) ;

		FOR(i, 1, n) {
			for(int id : pos[i - 1]) {
				st.up(id, dp[id]) ;
			}

			dp[i] = 1 ;
			dp[i] = max(dp[i], st.get(1, 1, n, 1, max(0, i - L[i] - 1)) + 1) ;
		}

		cout << *max_element(dp + 1, dp + 1 + n) ;
	}
}

int32_t main (int argc, char* argv[]) {
    ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ; 

    #define task "kieuoanh"
    if(fopen(task".inp","r")) {
        freopen(task".inp","r",stdin) ; 
        freopen(task".out","w",stdout) ; 
    }

    int tc ; tc = 1 ;
    if(watbor) cin >> tc ;

    FOR(bqc, 1, tc) {
        init() ;
        // if(subtask_1::check()) return subtask_1::solve(), 0 ;
        // if(subtask_2::check()) return subtask_2::solve(), 0 ;
        if(subtask_3::check()) return subtask_3::solve(), 0 ;
    }

    cerr << "\nTime : " << clock() * 0.001 << "s" << endl ;
    return 0 ; 
}
/* Watbor */

Compilation message (stderr)

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

• Subtask 1: 8 / 8
• Subtask 2: 16 / 16
• Subtask 3: 28 / 28
• Subtask 4: 18 / 18
• Subtask 5: 30 / 30