Submission #757670

#	Time	Username	Problem	Language	Result	Execution time	Memory
757670		maomao90	Tortoise (CEOI21_tortoise)	C++17	100 / 100	399 ms	24784 KiB

tortoise

    // Hallelujah, praise the one who set me free
    // Hallelujah, death has lost its grip on me
    // You have broken every chain, There's salvation in your name
    // Jesus Christ, my living hope
    #include <bits/stdc++.h> 
    using namespace std;
     
    #define REP(i, s, e) for (int i = (s); i < (e); i++)
    #define RREP(i, s, e) for (int i = (s); i >= (e); i--)
    template <class T>
    inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
    template <class T>
    inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
    typedef long long ll;
    typedef long double ld;
    #define FI first
    #define SE second
    typedef pair<int, int> ii;
    typedef pair<ll, ll> pll;
    typedef tuple<int, int, int> iii;
    #define ALL(_a) _a.begin(), _a.end()
    #define SZ(_a) (int) _a.size()
    #define pb push_back
    typedef vector<int> vi;
    typedef vector<ll> vll;
    typedef vector<ii> vii;
    typedef vector<iii> viii;
     
    #ifndef DEBUG
    #define cerr if (0) cerr
    #endif
     
    const int INF = 1000000005;
    const ll LINF = 1000000000000000005ll;
    const int MAXN = 500005;
     
    int n;
    int a[MAXN];
    int lft[MAXN], rht[MAXN];
    int grp[MAXN], cnt[MAXN];
    bool done[MAXN];
    int donewalk[MAXN];
    ll ans;
     
    int fw[MAXN];
    void fincre(int i, int x) {
        i++;
        for (; i <= n; i += i & -i) {
            fw[i] += x;
        }
    }
    void fincre(int s, int e, int x) {
        fincre(s, x);
        fincre(e + 1, -x);
    }
    int fqsm(int i) {
        i++;
        int res = 0;
        for (; i > 0; i -= i & -i) {
            res += fw[i];
        }
        return res;
    }
     
    #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
    int st[MAXN * 4], lz[MAXN * 4];
    void propo(int u, int lo, int hi) {
        if (lz[u] == 0) {
            return;
        }
        MLR;
        st[lc] += lz[u];
        lz[lc] += lz[u];
        st[rc] += lz[u];
        lz[rc] += lz[u];
        lz[u] = 0;
    }
    void upd(int p, int x, int u = 1, int lo = 0, int hi = n - 1) {
        if (lo == hi) {
            st[u] = x;
            return;
        }
        MLR;
        propo(u, lo, hi);
        if (p <= mid) {
            upd(p, x, lc, lo, mid);
        } else {
            upd(p, x, rc, mid + 1, hi);
        }
        st[u] = min(st[lc], st[rc]);
    }
    void incre(int s, int e, int x, int u = 1, int lo = 0, int hi = n - 1) {
        if (lo >= s && hi <= e) {
            st[u] += x;
            lz[u] += x;
            return;
        }
        MLR;
        propo(u, lo, hi);
        if (s <= mid) {
            incre(s, e, x, lc, lo, mid);
        }
        if (e > mid) {
            incre(s, e, x, rc, mid + 1, hi);
        }
        st[u] = min(st[lc], st[rc]);
    }
    int qmn(int s, int e, int u = 1, int lo = 0, int hi = n - 1) {
        if (lo >= s && hi <= e) {
            return st[u];
        }
        MLR;
        propo(u, lo, hi);
        int res = INF;
        if (s <= mid) {
            mnto(res, qmn(s, e, lc, lo, mid));
        }
        if (e > mid) {
            mnto(res, qmn(s, e, rc, mid + 1, hi));
        }
        return res;
    }
     
    int main() {
    #ifndef DEBUG
        ios::sync_with_stdio(0), cin.tie(0);
    #endif
        cin >> n;
        ll tot = 0;
        REP (i, 0, n) {
            cin >> a[i];
            if (a[i] > 0) {
                tot += a[i];
            }
        }
        int prv = -INF;
        int gc = 0;
        REP (i, 0, n) {
            if (a[i] == -1) {
                prv = i;
                gc++;
            }
            lft[i] = prv;
            grp[i] = gc;
        }
        prv = INF;
        RREP (i, n - 1, 0) {
            if (a[i] == -1) {
                prv = i;
            }
            rht[i] = prv;
        }
        vi id, pos;
        REP (i, 0, n) {
            if (a[i] <= 0) {
                continue;
            }
            cnt[grp[i]]++;
            id.pb(i);
            pos.pb(i);
        }
        sort(ALL(id), [&] (int l, int r) {
                return ii{min(l - lft[l], rht[l] - l), -l} < 
                ii{min(r - lft[r], rht[r] - r), -r};
                });
        REP (i, 1, n) {
            fincre(i, n - 1, 1);
        }
        REP (i, 0, n) {
            upd(i, INF);
        }
        for (int i : id) {
            cerr << i << '\n';
            done[i] = 1;
            int w = 2 * min(i - lft[i], rht[i] - i);
            // x <= a[i]
            int mn = qmn(i + 1, n - 1);
            assert(mn >= 0);
            // x * w <= mn
            // x <= floor(mn / w)
            int x1 = mn / w;
            int ct = fqsm(i);
            if (ct > 2 * i) {
                continue;
            }
            if (i - lft[i] <= rht[i] - i) { // left cycle
                if (donewalk[grp[i]] && donewalk[grp[i]] < i) {
                    continue;
                }
                auto apply = [&] (int x, bool walk) {
                    if (x + walk == 0) {
                        return;
                    }
                    if (walk) {
                        donewalk[grp[i]] = i;
                    }
                    cerr << "APPLY: " << x << ' ' << walk << '\n';
                    ans += x + walk;
                    fincre(i, n - 1, x * w);
                    incre(i, n - 1, -x * w);
                    // ct + (x - 1) * w + upd <= 2 * i
                    assert(ct + (x - 1 + walk) * w <= 2 * i);
                    upd(i, 2 * i - (ct + (x - 1 + walk) * w));
                };
                // ct + (x - 1) * w <= 2 * i
                // x <= (2 * i - ct) / w + 1
                int x2 = (2 * i - ct) / w + 1;
                if (a[i] < min(x1, x2)) {
                    auto ptr = upper_bound(ALL(pos), i);
                    bool walk = 0;
                    if (ptr == pos.end() || grp[*ptr] != grp[i] || done[*ptr]) {
                        walk = 1;
                    }
                    if (donewalk[grp[i]]) {
                        walk = 0;
                    }
                    apply(a[i] - walk, walk);
                    continue;
                } 
                if (rht[i] == INF) {
                    apply(min(x1, x2), 0);
                    continue;
                }
                if (x1 < x2) { // stopped by suffix but still have extra for walk
                    auto ptr = upper_bound(ALL(pos), i);
                    bool walk = 0;
                    if (ptr == pos.end() || grp[*ptr] != grp[i] || done[*ptr]) {
                        walk = 1;
                    }
                    if (donewalk[grp[i]]) {
                        walk = 0;
                    }
                    if (a[i] == x1 && walk) {
                        apply(x1 - 1, 1);
                    } else {
                        apply(x1, walk);
                    }
                    continue;
                }
                // no extra for walk unless replace one cycle with walk
                int nct = ct + x2 * w;
                // nct + j - i <= 2 * j
                // nct - i <= j
                int j = nct - i;
                auto ptr = lower_bound(ALL(pos), j);
                bool walk = 0;
                if (ptr == pos.end() || grp[*ptr] != grp[i] || done[*ptr]) {
                    walk = 1;
                }
                if (donewalk[grp[i]]) {
                    walk = 0;
                }
                apply(x2 - walk, walk);
            } else { // right cycle
                if (donewalk[grp[i]] && donewalk[grp[i]] > i) {
                    continue;
                }
                auto apply = [&] (int x) {
                    if (x == 0) {
                        return;
                    }
                    cerr << "APPLY: " << x << '\n';
                    ans += x;
                    fincre(i, n - 1, x * w);
                    incre(i, n - 1, -x * w);
                    // ct + x * w + upd <= 2 * i
                    assert(ct + x * w <= 2 * i);
                    upd(i, 2 * i - (ct + x * w));
                };
                auto ptr = lower_bound(ALL(pos), i);
                bool walk = 0;
                if (ptr == pos.begin() || grp[*prev(ptr)] != grp[i] || 
                        done[*prev(ptr)] || fqsm(*prev(ptr)) > 2 * (*prev(ptr))) {
                    walk = 1;
                }
                if (donewalk[grp[i]]) {
                    walk = 0;
                }
                if (walk) {
                    cerr << "WALK\n";
                    donewalk[grp[i]] = i;
                    a[i]--;
                    ans++;
                    // ct + upd <= 2 * i
                    upd(i, 2 * i - ct);
                }
                // ct + x * w <= 2 * i
                // x <= (2 * i - ct) / w
                int x2 = (2 * i - ct) / w;
                apply(min({a[i], x1, x2}));
            }
        }
        cout << tot - ans << '\n';
        return 0;
    }

Compilation message (stderr)

tortoise.cpp: In function 'void propo(int, int, int)':
tortoise.cpp:65:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |     #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                           ~~~^~~~
tortoise.cpp:71:9: note: in expansion of macro 'MLR'
   71 |         MLR;
      |         ^~~
tortoise.cpp:65:21: warning: unused variable 'mid' [-Wunused-variable]
   65 |     #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                     ^~~
tortoise.cpp:71:9: note: in expansion of macro 'MLR'
   71 |         MLR;
      |         ^~~
tortoise.cpp: In function 'void upd(int, int, int, int, int)':
tortoise.cpp:65:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |     #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                           ~~~^~~~
tortoise.cpp:83:9: note: in expansion of macro 'MLR'
   83 |         MLR;
      |         ^~~
tortoise.cpp: In function 'void incre(int, int, int, int, int, int)':
tortoise.cpp:65:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |     #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                           ~~~^~~~
tortoise.cpp:98:9: note: in expansion of macro 'MLR'
   98 |         MLR;
      |         ^~~
tortoise.cpp: In function 'int qmn(int, int, int, int, int)':
tortoise.cpp:65:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |     #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                           ~~~^~~~
tortoise.cpp:112:9: note: in expansion of macro 'MLR'
  112 |         MLR;
      |         ^~~

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 25 / 25
• Subtask 5: 27 / 27