Submission #1052475

#TimeUsernameProblemLanguageResultExecution timeMemory
1052475PhuocMoney (IZhO17_money)C++14
0 / 100
3 ms20060 KiB
#include <bits/stdc++.h> #include <iostream> #include <cmath> #include <iomanip> #include <vector> #include <map> #include <stack> #include <queue> #include <set> using namespace std; #define ll long long #define pb push_back #define el '\n' #define mpair make_pair #define MASK(i) (1LL << (i)) #define BIT(mask, i) (((mask) >> (i)) & 1) #define fi first #define se second #define all(v) v.begin(), v.end() /* Author: Pham Gia Phuoc */ const ll MOD = (ll)(1e9) + 7LL; template <class T1, class T2> void add(T1 &a, T2 b){ a += b; if(a >= MOD) a -= MOD; } template <class T1, class T2> void sub(T1 &a, T2 b){ a -= b; if(a < 0) a += MOD; } template <class T1, class T2> bool minimize(T1 &a, T2 b){ if(a > b){a = b; return true;} return false; } template <class T1, class T2> bool maximize(T1 &a, T2 b){ if(a < b){a = b; return true;} return false; } /** END OF TEMPLATE. DRINK A CUP OF COFFEE BEFORE READING MY CODE **/ const int MAX = (int)(1e6) + 10; const ll INF = (ll) 1e18 + 67LL; const int oo = (int)(1e9 + 7); const int NUM_BIT = 62; #define FOR(i, a, b) for(int i = a; i <= b; i++) #define FORD(i, a, b) for(int i = a; i >= b; i--) int n, a[MAX]; void init(){ cin >> n; FOR(i, 1, n) cin >> a[i]; } namespace subtask1{ bool check(){ return n <= 1e3; } const int MAXN = (int)(1e3) + 10; vector <int> cur[MAXN]; int dp[MAXN]; void solve(){ FOR(i, 1, n){ FOR(j, 1, i){ cur[i].push_back(a[j]); } sort(cur[i].begin(), cur[i].end()); cur[i].resize(unique(cur[i].begin(), cur[i].end()) - cur[i].begin()); } dp[0] = 0; FOR(i, 1, n){ dp[i] = dp[i - 1] + 1; FORD(j, i - 1, 1){ if(a[j] > a[j + 1]) break; if(a[j] == a[i]){ minimize(dp[i], dp[j - 1] + 1); continue; } int cnt = upper_bound(cur[j - 1].begin(), cur[j - 1].end(), a[i] - 1) - lower_bound(cur[j - 1].begin(), cur[j - 1].end(), a[j] + 1); if(cnt != 0) continue; minimize(dp[i], dp[j - 1] + 1); } } cout << dp[n]; } } namespace subtask2{ bool check(){ return n <= 1e6; } struct styn{ vector <int> IT; int n; styn(int _n = 0){ n = _n; IT.resize(n * 4 + 10, 0); } void Update(int p){ int i = 1, l = 1, r = n; while(l < r){ int m = (l + r) >> 1; if(p > m){l = m + 1; i = i * 2 + 1;} else{r = m; i = i * 2;} } IT[i]++; while(i > 1){ i >>= 1; IT[i] = IT[i * 2] + IT[i * 2 + 1]; } } int Get(int i, int l, int r, int u, int v){ if(l > v || r < u) return 0; if(u <= l && r <= v) return IT[i]; int m = (l + r) >> 1; return Get(i * 2, l, m, u, v) + Get(i * 2 + 1, m + 1, r, u, v); } }; int dp[MAX]; void solve(){ int ma = a[max_element(a + 1, a + n + 1) - a]; styn tree(ma); memset(dp, 0x3f, sizeof dp); dp[0] = 0; for(int i = 1, j = 1; i <= n; i++){ while(j < i && a[i] < a[i - 1]) tree.Update(a[j++]); while(j < i && tree.Get(1, 1, n, a[j] + 1, a[i] - 1) != 0) tree.Update(a[j++]); minimize(dp[i], dp[j - 1] + 1); } cout << dp[n]; } } void solve(){ // if(subtask1::check()){subtask1::solve(); return;} if(subtask2::check()){subtask2::solve(); return;} } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define test "test" // freopen(test".inp", "r", stdin); // freopen(test".out", "w", stdout); srand(time(0)); int t = 1; while(t--){ init(); solve(); } return 0; } /*** ROAD TO VOI 2025 ***/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...