oj.uz

Submission #342902

# Submission time Handle Problem Language Result Execution time Memory
342902 2021-01-03T07:57:38 Z maskoff Money (IZhO17_money) C++14
0 / 100
 10 ms 15980 KB 
#include <bits/stdc++.h>
 
#define file ""
 
#define all(x) x.begin(), x.end()
 
#define sc second
#define fr first
 
#define pb push_back
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
const ll inf = 1e18 + 5;
const ll mod = 1e9 + 7;
 
const int N = 1e6 + 5;
 
int dx[] = {+1, 0, -1, 0};
int dy[] = {0, +1, 0, -1};
 
int n;
int a[N], l[N];
vector<int> t(N * 4, 1e9);
           
void update(int u, int l, int r, int pos, int val) {
 	if (l == r) {
 	 	t[u] = val;
		return;
 	}
 	int m = l + r >> 1;
 	if (pos <= m) update(u + u, l, m, pos, val);
 	else update (u + u + 1, m + 1, r, pos, val);
 	t[u] = min(t[u + u], t[u + u + 1]);
}

int get(int u, int ul, int ur, int l, int r) {
 	if (l > ur || ul > r) return 1e9;
 	if (l <= ul && ur <= r) return t[u];
 	int um = ul + ur >> 1;
 	return min(get(u + u, ul, um, l, r), get(u + u + 1, um + 1, ur, l, r));
}

            
int main() {  
	ios_base :: sync_with_stdio(false);               
	cin.tie(nullptr);
	srand(time(nullptr));
	cin >> n;
	vector<int> dp(n + 5);
	for (int i = 1; i <= n; i++) cin >> a[i];

	l[1] = 1;
	int last = 1;
	for (int i = 2; i <= n; i++) {
   	if (a[i] >= a[i - 1])  continue;
  	else {
  		for (int p = last; p <= i - 1; p++)
  			l[p] = last;
  		last = i;
  	}
  }
  for (int p = last; p <= n; p++) l[p] = last;
  update(1, 1, n, 1, 0);
  dp[1] = 1;
  for (int i = 2; i <= n; i++) {
  	update(1, 1, n, i, dp[i - 1]);
  	dp[i] = get(1, 1, n, l[i], i) + 1;
  }
  cout << dp[n];
  return 0;
}

Compilation message

money.cpp: In function 'void update(int, int, int, int, int)':
money.cpp:35:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int m = l + r >> 1;
      |           ~~^~~
money.cpp: In function 'int get(int, int, int, int, int)':
money.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |   int um = ul + ur >> 1;
      |            ~~~^~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15980 KB Output is correct
2 Incorrect 10 ms 15980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15980 KB Output is correct
2 Incorrect 10 ms 15980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15980 KB Output is correct
2 Incorrect 10 ms 15980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15980 KB Output is correct
2 Incorrect 10 ms 15980 KB Output isn't correct
3 Halted 0 ms 0 KB -