oj.uz

Submission #644710

# Submission time Handle Problem Language Result Execution time Memory
644710 2022-09-25T06:33:51 Z ghostwriter Money (IZhO17_money) C++14
0 / 100
 15 ms 23892 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define FSN(i, n) for (int (i) = (n) - 1; (i) >= 0; --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Tran The Bao - ghostwriter
    Training for VOI23 gold medal
----------------------------------------------------------------
    DIT ME CHUYEN BAO LOC
----------------------------------------------------------------
*/
const int oo = 1e9 + 5;
struct Node {
	int opt, left, right;
	Node() : opt(oo), left(0), right(0) {}
	Node(int opt, int left, int right) : opt(opt), left(left), right(right) {}
};
const int N = 1e6 + 5;
const int Nx2 = 2e6 + 5;
int n, a[N], r[N], d[N], root = 0, cnt = 0;
multiset<int> s;
Node tr[Nx2];
void upd(int &i, int l, int r, int q, int v) {
	if (!i) i = ++cnt;
	if (r < q || l > q) return;
	if (l == r) {
		tr[i].opt = min(tr[i].opt, v);
		return;
	}
	int mid = l + (r - l) / 2;
	upd(tr[i].left, l, mid, q, v);
	upd(tr[i].right, mid + 1, r, q, v);
	tr[i].opt = min(tr[tr[i].left].opt, tr[tr[i].right].opt);
}
int get(int &i, int l, int r, int ql, int qr) {
	if (!i) i = ++cnt;
	if (r < ql || l > qr) return oo;
	if (ql <= l && r <= qr) return tr[i].opt;
	int mid = l + (r - l) / 2;
	return min(get(tr[i].left, l, mid, ql, qr), get(tr[i].right, mid + 1, r, ql, qr));
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    cin >> n;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, n) {
    	r[i] = max(r[i - 1], i);
    	WHILE(r[i] < n && a[r[i]] <= a[r[i] + 1]) {
    		if (a[r[i]] == a[r[i] + 1]) {
    			++r[i];
    			continue;
    		}
    		if (s.empty() || *--s.ed() <= a[r[i]]) {
    			++r[i];
    			continue;
    		}
			int v = *s.ub(a[r[i]]);
			if (v < a[r[i] + 1]) break;
			++r[i];
    	}
    	s.insert(a[i]);
    }
    d[n] = 1;
    upd(root, 1, n, n, d[n]);
    FOS(i, n - 1, 1) {
    	if (r[i] == n) d[i] = 1;
    	else d[i] = get(root, 1, n, i + 1, r[i] + 1) + 1;
    	upd(root, 1, n, i, d[i]);
    }
    cout << d[1];
    return 0;
}
/*
6
3 6 4 5 1 2
----------------------------------------------------------------
From Benq:
    stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
        * DON'T GET STUCK ON ONE APPROACH
----------------------------------------------------------------
*/

Compilation message

money.cpp: In function 'int main()':
money.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
money.cpp:84:5: note: in expansion of macro 'FOR'
   84 |     FOR(i, 1, n) cin >> a[i];
      |     ^~~
money.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
money.cpp:85:5: note: in expansion of macro 'FOR'
   85 |     FOR(i, 1, n) {
      |     ^~~
money.cpp:31:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   31 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
      |                               ^
money.cpp:104:5: note: in expansion of macro 'FOS'
  104 |     FOS(i, n - 1, 1) {
      |     ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23776 KB Output is correct
3 Correct 11 ms 23716 KB Output is correct
4 Correct 11 ms 23820 KB Output is correct
5 Correct 15 ms 23764 KB Output is correct
6 Correct 12 ms 23792 KB Output is correct
7 Correct 11 ms 23808 KB Output is correct
8 Correct 12 ms 23892 KB Output is correct
9 Correct 11 ms 23892 KB Output is correct
10 Correct 11 ms 23764 KB Output is correct
11 Correct 11 ms 23764 KB Output is correct
12 Incorrect 12 ms 23724 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23776 KB Output is correct
3 Correct 11 ms 23716 KB Output is correct
4 Correct 11 ms 23820 KB Output is correct
5 Correct 15 ms 23764 KB Output is correct
6 Correct 12 ms 23792 KB Output is correct
7 Correct 11 ms 23808 KB Output is correct
8 Correct 12 ms 23892 KB Output is correct
9 Correct 11 ms 23892 KB Output is correct
10 Correct 11 ms 23764 KB Output is correct
11 Correct 11 ms 23764 KB Output is correct
12 Incorrect 12 ms 23724 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23776 KB Output is correct
3 Correct 11 ms 23716 KB Output is correct
4 Correct 11 ms 23820 KB Output is correct
5 Correct 15 ms 23764 KB Output is correct
6 Correct 12 ms 23792 KB Output is correct
7 Correct 11 ms 23808 KB Output is correct
8 Correct 12 ms 23892 KB Output is correct
9 Correct 11 ms 23892 KB Output is correct
10 Correct 11 ms 23764 KB Output is correct
11 Correct 11 ms 23764 KB Output is correct
12 Incorrect 12 ms 23724 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23776 KB Output is correct
3 Correct 11 ms 23716 KB Output is correct
4 Correct 11 ms 23820 KB Output is correct
5 Correct 15 ms 23764 KB Output is correct
6 Correct 12 ms 23792 KB Output is correct
7 Correct 11 ms 23808 KB Output is correct
8 Correct 12 ms 23892 KB Output is correct
9 Correct 11 ms 23892 KB Output is correct
10 Correct 11 ms 23764 KB Output is correct
11 Correct 11 ms 23764 KB Output is correct
12 Incorrect 12 ms 23724 KB Output isn't correct
13 Halted 0 ms 0 KB -