oj.uz

Submission #644729

# Submission time Handle Problem Language Result Execution time Memory
644729 2022-09-25T06:51:33 Z ghostwriter Money (IZhO17_money) C++14
9 / 100
 14 ms 23868 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], c[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;
			if (a[r[i]] == a[i]) {
				++r[i];
				continue;
			}
			if (c[a[r[i]]]) break;
			++r[i];
    	}
    	s.insert(a[i]);
    	++c[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:110:5: note: in expansion of macro 'FOS'
  110 |     FOS(i, n - 1, 1) {
      |     ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 12 ms 23832 KB Output is correct
3 Correct 11 ms 23712 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 11 ms 23792 KB Output is correct
6 Correct 13 ms 23752 KB Output is correct
7 Correct 11 ms 23764 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 12 ms 23800 KB Output is correct
10 Correct 11 ms 23764 KB Output is correct
11 Correct 14 ms 23764 KB Output is correct
12 Correct 11 ms 23788 KB Output is correct
13 Correct 11 ms 23756 KB Output is correct
14 Correct 11 ms 23764 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 11 ms 23868 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 12 ms 23832 KB Output is correct
3 Correct 11 ms 23712 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 11 ms 23792 KB Output is correct
6 Correct 13 ms 23752 KB Output is correct
7 Correct 11 ms 23764 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 12 ms 23800 KB Output is correct
10 Correct 11 ms 23764 KB Output is correct
11 Correct 14 ms 23764 KB Output is correct
12 Correct 11 ms 23788 KB Output is correct
13 Correct 11 ms 23756 KB Output is correct
14 Correct 11 ms 23764 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 11 ms 23868 KB Output is correct
17 Incorrect 11 ms 23776 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 12 ms 23832 KB Output is correct
3 Correct 11 ms 23712 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 11 ms 23792 KB Output is correct
6 Correct 13 ms 23752 KB Output is correct
7 Correct 11 ms 23764 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 12 ms 23800 KB Output is correct
10 Correct 11 ms 23764 KB Output is correct
11 Correct 14 ms 23764 KB Output is correct
12 Correct 11 ms 23788 KB Output is correct
13 Correct 11 ms 23756 KB Output is correct
14 Correct 11 ms 23764 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 11 ms 23868 KB Output is correct
17 Incorrect 11 ms 23776 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 12 ms 23832 KB Output is correct
3 Correct 11 ms 23712 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 11 ms 23792 KB Output is correct
6 Correct 13 ms 23752 KB Output is correct
7 Correct 11 ms 23764 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 12 ms 23800 KB Output is correct
10 Correct 11 ms 23764 KB Output is correct
11 Correct 14 ms 23764 KB Output is correct
12 Correct 11 ms 23788 KB Output is correct
13 Correct 11 ms 23756 KB Output is correct
14 Correct 11 ms 23764 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 11 ms 23868 KB Output is correct
17 Incorrect 11 ms 23776 KB Output isn't correct
18 Halted 0 ms 0 KB -