Submission #1326387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326387		retarde	Snail (NOI18_snail)	C++20	0 / 100	1 ms	1336 KiB

snail

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

#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define int long long
#define all(x) (x).begin(), (x).end()

typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;

const int mod = 1e9 + 7;
const int inf = INTMAX_MAX;
const bool tc = false;

struct Segtree {
    int n;
    vector<int> st, lz, a;

    Segtree() : n(0) {}
    Segtree(const vector<int>& init) { build_from_array(init); }

    void init(int n_) {
        n = n_;
        st.assign(4 * n + 5, 0);
        lz.assign(4 * n + 5, 0);
        a.assign(n, 0);
    }

    void build_from_array(const vector<int>& init) {
        int sz = init.size();
        init_tree(init, sz);
    }

    void init_tree(const vector<int>& arr, int sz) {
        init(sz);
        a = arr;

        vector<int> pref(n);
        pref[0] = a[0];
        for (int i = 1; i < n; i++) pref[i] = pref[i - 1] + a[i];

        build(1, 0, n - 1, pref);
    }

    void build(int p, int l, int r, const vector<int>& arr) {
        if (l == r) {
            st[p] = arr[l];
            return;
        }
        int m = (l + r) >> 1;
        build(p << 1, l, m, arr);
        build(p << 1 | 1, m + 1, r, arr);
        st[p] = max(st[p << 1], st[p << 1 | 1]);
    }

    void apply(int p, int v) {
        st[p] += v;
        lz[p] += v;
    }

    void push(int p) {
        if (lz[p] != 0) {
            apply(p << 1, lz[p]);
            apply(p << 1 | 1, lz[p]);
            lz[p] = 0;
        }
    }

    void range_add(int ql, int qr, int v) {
        range_add(1, 0, n - 1, ql, qr, v);
    }

    void range_add(int p, int l, int r, int ql, int qr, int v) {
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            apply(p, v);
            return;
        }
        push(p);
        int m = (l + r) >> 1;
        range_add(p << 1, l, m, ql, qr, v);
        range_add(p << 1 | 1, m + 1, r, ql, qr, v);
        st[p] = max(st[p << 1], st[p << 1 | 1]);
    }

    int range_max(int ql, int qr) {
        if (qr < 0) return 0;
        return range_max(1, 0, n - 1, ql, qr);
    }

    int range_max(int p, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return LLONG_MIN;
        if (ql <= l && r <= qr) return st[p];
        push(p);
        int m = (l + r) >> 1;
        return max(range_max(p << 1, l, m, ql, qr),
                   range_max(p << 1 | 1, m + 1, r, ql, qr));
    }

    void point_set(int pos, int val) {
        int delta = val - a[pos];
        a[pos] = val;
        range_add(pos, n - 1, delta);
    }

    int max_prefix_sum(int l, int r) {
        return range_max(l, r);
    }
};

int cdiv(int x, int y) {
    return (x + (y - 1)) / y;
}

inline void solve() {
    int n, h;
    cin >> h >> n;
    vi a(n); for (int i = 0; i < n; i++) cin >> a[i];
    priority_queue<int, vector<int>, greater<int>> c; vi p(n); p[0] = max(a[0], (int)0);
    if (a[0] < 0) c.push(0);

    int cur = p[0];
    for (int i = 1; i < n; i++) {
        if (cur + a[i] < 0) {
            p[i] = -cur;
            cur = 0;
            c.push(i);
        } else {   
            p[i] = a[i];
            cur += a[i];
        }
    }

    // for (auto &x : p) cout << x << " ";
    // cout << '\n';

    Segtree st(p);

    int bal = 0;
    int day = 0; int bad = 0; bool ok = true;

    int itr = 0;
    while (true) {
        // cout << "itr " << itr << '\n';

        if (bal + st.range_max(0, n - 1) >= h) {
            break;
        }

        if (!c.size()) {
            // cout << "emptied\n";
            break;
        }
        if (bad >= 2) {
            // cout << "i aint doing shit\n";
            ok = false;
            break;
        }
        int done = 0;
        while (c.size()) {
            int x = c.top();
            // cout << x << " x clamp\n";
            int sm = st.range_max(x - 1, x - 1);
            if (sm + bal + a[x] >= 0) {
                // cout << "ts so sigma i win\n";
                p[x] = a[x];
                st.point_set(x, a[x]);
                c.pop();
                done++;
            } else {
                // cout << "not tuff still resetted\n";
                break;
            }
        }

        bal += st.range_max(n - 1, n - 1);
        if (done == 0) {bad++;}
        day++;
    }

    if (!ok) {
        cout << "-1 -1\n";
        return;
    }

    // cout << "its day " << day << " and my bal " << bal << '\n';
    int peak = st.range_max(0, n - 1);
    int loop = cdiv(((h - peak) - bal), st.range_max(n - 1, n - 1));
    day += loop; bal += loop * st.range_max(n - 1, n - 1);
    for (int i = 0; i < n; i++) {
        if (bal + st.range_max(i, i) >= h) {
            cout << day << " " << i << '\n';
            return;
        }
    }
    cout << "wtf\n";
    assert(false);
}

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

signed main() {
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    //setIO();

    int t = 1;
    if (tc) {
        cin >> t;
    }

    while (t--) {
        solve();
    }
}

Compilation message (stderr)

snail.cpp: In function 'void setIO(std::string)':
snail.cpp:219:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  219 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
snail.cpp:220:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  220 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 9
• Subtask 3: 0 / 25
• Subtask 4: 0 / 17
• Subtask 5: 0 / 38