Submission #158006

#TimeUsernameProblemLanguageResultExecution timeMemory
158006hentai_loverMoney (IZhO17_money)C++14
45 / 100
668 ms21312 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #define lft(x) x * 2 #define rgt(x) x * 2 + 1 #define tm hui_pizda #define ft first #define sd second #define pb push_back #define pf push_front #define sz size() #define cnt continue #define m_p make_pair #define fr(i, l, r) for(int i = l; i <= r; ++ i) #define rf(i, r, l) for(int i = r; i >= l; -- i) #define all(x) x.begin(), x.end() #pragma GCC optimize(-O3) #pragma GCC optimize(Ofast) #pragma GCC optimize("unroll-loops") using namespace __gnu_pbds; using namespace std; template <typename T> using _set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; typedef long double ld; typedef pair <ll, ll> pll; typedef pair <int, int> pii; typedef vector <int> vi; typedef vector <ll> vl; typedef vector <pii> vpi; typedef vector <pll> vpl; mt19937_64 rnd(time(NULL)); const ll N = 1e6; const ll mtrxN = 10; const ll oo = 1e18 + 10; const ll B = 500; const ll mod = 1e9 + 7; struct mtrx{ ll m[mtrxN][mtrxN] = {}; }; mtrx mtrx_mult(mtrx a, mtrx b){ mtrx c; fr(i, 0, mtrxN - 1){ fr(j, 0, mtrxN - 1){ ll sum = 0; fr(x, 0, mtrxN - 1){ sum += a.m[i][x] * b.m[x][j]; sum %= mod; } c.m[i][j] = sum; } } return c; } mtrx mtrx_pow(mtrx a, ll n){ mtrx res; fr(i, 0, mtrxN - 1)fr(j, 0, mtrxN - 1)res.m[i][j] = a.m[i][j]; n --; while(n){ if(n&1)res = mtrx_mult(res, a); a = mtrx_mult(a, a); n >>= 1; } return res; } ll _pow(ll a, ll n){ ll r = 1; while(n){ if(n&1)r = r * a % mod; a = a * a % mod; n >>= 1; } return r; } ll div(ll x, ll y, ll md){ return x * _pow(y, md - 2) % md; } ll dp[N], a[N], p[N]; ll n; set <ll> s; vl v; int main(){ //NN = 10000; cin >> n; fr(i, 1, n)cin >> a[i]; fr(i, 1, n - 1){ if(a[i] > a[i + 1])v.pb(i); } fr(i, 1, n)dp[i] = oo; dp[0] = 0; fr(i, 0, n - 1){ ll l = i + 1, r, t, z = -1; auto j = upper_bound(v.begin(), v.end(), i); if(j == v.end())r = n; else r = *j; auto it = s.upper_bound(a[i + 1]); if(it == s.end())t = oo; else t = *it; //cout << "i: " << i << ' '<< l << ' ' << r << endl; while(l <= r){ ll c = (l + r) / 2; if(a[c] <= t)l = c + 1, z = c; else r = c - 1; } //cout << "i: " << i << " z: " << z << endl; dp[z] = min(dp[z], dp[i] + 1); s.insert(a[i + 1]); } // fr(i, 1, n)cout << dp[i] << ' '; // cout << endl; cout << dp[n] << endl; return 0; } /* 6 1 2 6 3 4 5 */

Compilation message (stderr)

money.cpp:18:22: warning: '#pragma GCC optimize' is not a string or number [-Wpragmas]
 #pragma GCC optimize(-O3)
                      ^
money.cpp:19:22: warning: '#pragma GCC optimize' is not a string or number [-Wpragmas]
 #pragma GCC optimize(Ofast)
                      ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...