제출 #1294638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1294638		ayaz	Money (IZhO17_money)	C++20	100 / 100	461 ms	20008 KiB

money

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define ll long long
#define ld long double
#define pii pair<int,int>
#define all(x) (x).begin(), (x).end()
#define isz(x) (int)(x.size())
#define vi vector<int>

template<typename T>
using ost = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int sz = 1e6+10, inf = 1e9;
const ll mod = 1e9+7, INF = 1e18;

int a[sz];
int st[sz<<2];
void update(int l, int r, int v, int pos, int val){
    if (l > pos || pos > r) return;
    if (l == r) {
        st[v] = (st[v] > val ? val : st[v]);
        return;
    }
    int mid = (l+r)>>1;
    update(l, mid, v<<1, pos, val);
    update(mid+1, r, v<<1|1, pos, val);
    st[v] = min(st[v<<1], st[v<<1|1]);
}
int getans(int l, int r, int ql, int qr, int v) {
    if (r < ql || l > qr) return inf;
    if (ql <= l && r <= qr) return st[v];
    int mid = (l+r)>>1;
    return min(getans(l, mid, ql, qr, v<<1), getans(mid+1, r, ql, qr, v<<1|1));
}
void solve(int tc) {
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    fill(st, st+(sz<<2), inf);
    int ans = 0, idx = 1;
    int l = 1, r = 1;
    auto check = [&](int i, int j){
        if (a[i] == a[j] || a[j] - a[i] == 1) return true;
        int res = getans(1, sz, a[i]+1, a[j]-1, 1);
        return (res == idx || res == inf);
    };
    while (r <= n) {
        int prev = 0;
        while (prev <= a[r] && r <= n && check(l, r)) {
            prev = a[r];
            update(1, sz, 1, a[r], idx);
            r++;
        }
        assert(a[l] <= a[r - 1]);
        l = r;
        ans++;
        idx++;
    }
    cout << ans << '\n';
}
void precompute() {}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("err.log", "w", stderr);
#endif    
    precompute();
    int t = 1;
    // cin >> t;
    for (int tc = 1; tc <= t; tc++) solve(tc);
    return 0;    
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55