Submission #1190293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190293		froxy09	Liteh and Newfiteh (INOI20_litehfiteh)	C++20	0 / 100	0 ms	320 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct SegTree {
    int n;
    vector<ll> mn, lz;
    SegTree(int _n, const vector<ll>& a) : n(_n) {
        mn.assign(4*n, 0);
        lz.assign(4*n, 0);
        build(1, 0, n-1, a);
    }
    void build(int node, int l, int r, const vector<ll>& a) {
        if (l == r) {
            mn[node] = a[l];
        } else {
            int mid = (l + r) >> 1;
            build(node<<1, l, mid, a);
            build(node<<1|1, mid+1, r, a);
            mn[node] = min(mn[node<<1], mn[node<<1|1]);
        }
    }
    void apply(int node, ll val) {
        mn[node] += val;
        lz[node] += val;
    }
    void push(int node) {
        if (lz[node] != 0) {
            apply(node<<1, lz[node]);
            apply(node<<1|1, lz[node]);
            lz[node] = 0;
        }
    }
    ll queryMin(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return LLONG_MAX;
        if (ql <= l && r <= qr) return mn[node];
        push(node);
        int mid = (l + r) >> 1;
        return min(queryMin(node<<1, l, mid, ql, qr),
                   queryMin(node<<1|1, mid+1, r, ql, qr));
    }
    void update(int node, int l, int r, int ql, int qr, ll val) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            apply(node, val);
            return;
        }
        push(node);
        int mid = (l + r) >> 1;
        update(node<<1, l, mid, ql, qr, val);
        update(node<<1|1, mid+1, r, ql, qr, val);
        mn[node] = min(mn[node<<1], mn[node<<1|1]);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    SegTree st(n, a);
    ll moves = 0;
    int maxk = 0;
    while ((1 << (maxk + 1)) <= n) maxk++;

    // Greedy: largest segments first
    for (int k = maxk; k >= 0; --k) {
        int len = 1 << k;
        for (int l = 0; l + len <= n; l += len) {
            int r = l + len - 1;
            if (st.queryMin(1, 0, n-1, l, r) > 0) {
                st.update(1, 0, n-1, l, r, -1);
                moves++;
            }
        }
    }

    // Check if any element remains positive -> impossible
    for (int i = 0; i < n; ++i) {
        if (st.queryMin(1, 0, n-1, i, i) > 0) {
            cout << -1;
            return 0;
        }
    }

    cout << moves;
    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70