Submission #1247994

#TimeUsernameProblemLanguageResultExecution timeMemory
1247994al95ireyizBouquet (EGOI24_bouquet)C++20
100 / 100
67 ms20212 KiB
//*** Bismillah ***// #pragma GCC optimize("O3", "fast-math", "unroll-loops", "no-stack-protector") #include <bits/stdc++.h> using namespace std; #if !defined(ONLINE_JUDGE) and !defined(EVAL) #include "template/debug.h" #else #define d(x...) #endif #define fr first #define er erase #define sc second #define in insert #define ll long long #define pb push_back #define vll vector<ll> #define pll pair<ll,ll> #define ull unsigned ll #define vpll vector<pll> #define len(x) (ll) x.size() #define all(x) x.begin(),x.end() const ll INF = 1e9; const ll INFL = 1e18; const ll MOD = 1e9+7; // const ll MOD = 998244353; const ll maxn = 2e5+5; ll n,m,k=0; ll l[maxn], r[maxn], dp[maxn], tree[4 * maxn]; void upd(ll x, ll val, ll l = 1, ll r = n, ll v = 1){ if(l == r){ tree[v] = val; return; } ll md = (l + r) >> 1; if(x <= md) upd(x, val, l, md, v << 1); else upd(x, val, md + 1, r, v << 1 | 1); tree[v] = max(tree[v << 1], tree[v << 1 | 1]); } ll get(ll _l, ll _r, ll l = 1, ll r = n, ll v = 1){ bool in = _l <= l and r <= _r; bool ot = _l <= r and l <= _r; if(in) return tree[v]; if(ot){ ll md = (l + r) >> 1; return max(get(_l, _r, l, md, v << 1), get(_l, _r, md + 1, r, v << 1 | 1)); } return 0; } vpll v[maxn]; void _(ll &tt){ cin >> n; for(ll i = 1; i <= n; i ++) cin >> l[i] >> r[i], l[i] = min(l[i], i - 1), r[i] = min(r[i], n - i), v[i].clear(); // if(max(l[i], r[j]) < i - j){ // if(max(l[i] - i + j, r[j] - i + j) < 0){ // if(l[i] - i + j < 0 ve r[j] - i + j < 0){ // if(l[i] + (j - i) < 0 ve r[j] + (j - i) < 0){ // if(i - l[i] > j >= 1 ve r[j] + j < i <= n){ // j -> [1, i - l[i] - 1] ve i -> [r[j] + j + 1, n] ll mx = 0; for(ll i = 1; i <= n; i ++){ for(auto [x, val] : v[i]){ upd(x, val); } dp[i] = get(1, i - l[i] - 1) + 1; v[r[i] + i + 1].pb({i, dp[i]}); mx = max(mx, dp[i]); d(dp[i]); } cout << mx << '\n'; } signed main() { ll tm = clock(); cin.tie(0)->sync_with_stdio(0); ll t = 1; // cin >> t; for(ll tt = 1; tt <= t; tt ++) { _(tt); } cerr << "\n\033[1;31mTime: \033[1;30m" \ << (double)(clock()-tm)/1000000 << "\033[1;32m seconds\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...