Submission #757620

#	Time	Username	Problem	Language	Result	Execution time	Memory
757620		maomao90	Tortoise (CEOI21_tortoise)	C++17	8 / 100	2 ms	2320 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], prvgrp[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 (s > e) {
        return;
    }
    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 (s > e) {
        return INF;
    }
    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;
        }
        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);
    }
    memset(prvgrp, -1, sizeof prvgrp);
    for (int i : id) {
        cerr << i << '\n';
        if (prvgrp[grp[i]] != -1) {
            int u = prvgrp[grp[i]];
            int w = 2 * min(u - lft[u], rht[u] - u);
            int mn = qmn(u + 1, n - 1);
            if (w > mn) {
                continue;
            }
            int ct = fqsm(u);
            // if right cycle and cannot replace walk with cycle
            // note that left cycle is always possible
            if (u - lft[u] > rht[u] - u && ct + w > 2 * u) {
                continue;
            }
            fincre(u, n - 1, w);
            if (u - lft[u] > rht[u] - u) {
                incre(u, n - 1, -w);
                cerr << "INCRE: " << u << ' ' << n - 1 << ' ' << -w << '\n';
            }
            ct = fqsm(i);
            if (ct > 2 * i) {
                fincre(u, n - 1, -w);
                if (u - lft[u] > rht[u] - u) {
                    incre(u, n - 1, w);
                    cerr << "INCRE: " << u << ' ' << n - 1 << ' ' << w << '\n';
                }
                continue;
            }
        }
        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
            auto apply = [&] (int x, bool walk) {
                if (x + walk == 0) {
                    return;
                }
                cerr << "APPLY: " << x << ' ' << walk << '\n';
                ans += x + walk;
                fincre(i, n - 1, x * w);
                incre(i, n - 1, -x * w);
                cerr << "INCRE: " << i << ' ' << n - 1 << ' ' << -x * w << '\n';
                // ct + (x - 1) * w + upd <= 2 * i
                assert(ct + (x - 1 + walk) * w <= 2 * i);
                cerr << "UPD: " << 2 * i - (ct + (x - 1 + walk) * w) << '\n';
                upd(i, 2 * i - (ct + (x - 1 + walk) * w));
            };
            if (rht[i] == INF) {
                // ct + (x - 1) * w <= 2 * i
                // x <= (2 * i - ct) / w + 1
                int x2 = (2 * i - ct) / w + 1;
                apply(min({a[i], x1, x2}), 0);
            } else {
                // ct + x * w <= 2 * i
                // x <= (2 * i - ct) / w
                int x2 = (2 * i - ct) / w;
                apply(min({a[i] - 1, x1, x2}), 1);
                prvgrp[grp[i]] = i;
            }
        } else { // right cycle
            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);
                cerr << "INCRE: " << i << ' ' << n - 1 << ' ' << -x * w << '\n';
                // ct + x * w + upd <= 2 * i
                assert(ct + x * w <= 2 * i);
                cerr << "UPD: " << 2 * i - (ct + x * w) << '\n';
                upd(i, 2 * i - (ct + x * w));
            };
            cerr << "WALK\n";
            prvgrp[grp[i]] = i;
            a[i]--;
            ans++;
            // ct + upd <= 2 * i
            upd(i, 2 * i - ct);
            cerr << "UPD: " << 2 * i - ct << '\n';
            // 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:64:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
tortoise.cpp:70:5: note: in expansion of macro 'MLR'
   70 |     MLR;
      |     ^~~
tortoise.cpp:64:17: warning: unused variable 'mid' [-Wunused-variable]
   64 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                 ^~~
tortoise.cpp:70:5: note: in expansion of macro 'MLR'
   70 |     MLR;
      |     ^~~
tortoise.cpp: In function 'void upd(int, int, int, int, int)':
tortoise.cpp:64:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
tortoise.cpp:82:5: note: in expansion of macro 'MLR'
   82 |     MLR;
      |     ^~~
tortoise.cpp: In function 'void incre(int, int, int, int, int, int)':
tortoise.cpp:64:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
tortoise.cpp:100:5: note: in expansion of macro 'MLR'
  100 |     MLR;
      |     ^~~
tortoise.cpp: In function 'int qmn(int, int, int, int, int)':
tortoise.cpp:64:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
tortoise.cpp:117:5: note: in expansion of macro 'MLR'
  117 |     MLR;
      |     ^~~

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