| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 684646 |
2023-01-22T09:02:42 Z |
pragmatist |
Money (IZhO17_money) |
C++17 |
|
12 ms |
15960 KB |
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#define sz(v) (int)v.size()
#define ll long long
#define pb push_back
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define nl "\n"
using namespace std;
const int N = (int)1e6 + 7; // make sure this is right
const int M = (int)1e7 + 7;
const int inf = (int)2e9 + 7;
const ll INF = (ll)3e18 + 7;
const ll MOD = (ll)1e9 + 7; // make sure this is right
bool bit(int x, int i) {
return x >> i & 1;
}
int sum(int x, int y) {
x += y;
if(x >= MOD) x -= MOD;
return x;
}
int n, a[N], dp[N], p[N];
int timer, tree[N], t[M], L[M], R[M], lim = 1e6;
void build(int v, int tl, int tr) {
if(tl == tr) {
return;
}
int mid = (tl + tr) >> 1;
L[v] = ++timer;
build(L[v], tl, mid);
R[v] = ++timer;
build(R[v], mid + 1, tr);
}
void upd(int prev, int v, int tl, int tr, int id) {
if(tl == tr) {
t[v] = t[prev] + 1;
return;
}
int mid = (tl + tr) >> 1;
if(id <= mid) {
L[v] = ++timer;
R[v] = R[prev];
upd(L[prev], L[v], tl, mid, id);
} else {
R[v] = ++timer;
L[v] = L[prev];
upd(R[prev], R[v], mid + 1, tr, id);
}
t[v] = t[L[v]] + t[R[v]];
}
int get(int v, int tl, int tr, int id) {
if(tl == tr) {
return tl;
}
int mid = (tl + tr) >> 1;
if(t[L[v]] >= mid) return get(L[v], tl, mid, id);
else return get(R[v], mid + 1, tr, id - t[L[v]]);
}
int get(int i, int j) {
return get(tree[i], 1, lim, j);
}
void solve() {
cin >> n;
tree[0] = ++timer;
build(1, 1, lim);
for(int i = 1; i <= n; ++i) {
cin >> a[i];
tree[i] = ++timer;
upd(tree[i - 1], tree[i], 1, lim, a[i]);
if(i > 1) p[i] = p[i - 1] + (a[i - 1] <= a[i]);
}
int j = 1;
for(int i = 1; i <= n; ++i) {
dp[i] = inf;
while(j <= i) {
if(p[i] - p[j] != i - j) {
j++;
continue;
}
bool can = (a[j] >= get(j - 1, j - 1) || a[i] <= get(j - 1, 1));
int l = 1, r = j - 2, k = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(a[i] <= get(j - 1, mid + 1)) {
k = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if(k != -1) {
can |= (a[j] >= get(j - 1, k));
}
if(can) {
dp[i] = min(dp[i], dp[j - 1] + 1);
break;
} else {
j++;
}
}
}
cout << dp[n];
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
int test = 1;
//cin >> test;
for(int i = 1; i <= test; ++i) {
//cout << "Case #" << i << ": ";
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
15956 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
15960 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
15956 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
15960 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
15956 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
15960 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
15956 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
15960 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
