Submission #473938

#	Time	Username	Problem	Language	Result	Execution time	Memory
473938		model_code	Tortoise (CEOI21_tortoise)	C++17	100 / 100	1096 ms	46924 KiB

tortoise

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

#define _ << " " <<

const int MAXN = 5e5 + 5;
const int off = 1 << 19;
const int inf = 1e9;

int a[MAXN];
int l[MAXN];
int r[MAXN];
int before[MAXN];

unordered_map<int, int> specialChair;

typedef pair<int, int> pii;

struct Tournament {
    vector<int> t;
    vector<int> p;

    Tournament() {
        t.resize(2 * off);
        p.resize(2 * off);
    }

    void init() {
        for (int i = off; i < 2 * off; ++i) {
            t[i] = inf + (i - off);
        }
        for (int i = off - 1; i; i--) {
            t[i] = min(t[i * 2], t[i * 2 + 1]);
        }
    }

    void prop(int x) {
        if (p[x]) {
            t[x] += p[x];
            if (x < off) {
                p[x * 2] += p[x];
                p[x * 2 + 1] += p[x];
            }
            p[x] = 0;
        }
    }

    void upd(int a, int b, int v, int x = 1, int lo = 0, int hi = off) {
        if (lo >= a && hi <= b) {
            p[x] += v;
            prop(x);
            return;
        }
        prop(x);
        if (lo >= b || hi <= a) return;
        int mi = (lo + hi) >> 1;
        upd(a, b, v, x * 2, lo, mi);
        upd(a, b, v, x * 2 + 1, mi, hi);
        t[x] = min(t[x * 2], t[x * 2 + 1]);
    }
    int get(int a, int b, int x = 1, int lo = 0, int hi = off) {
        if (lo >= b || hi <= a) return inf;
        prop(x);
        if (lo >= a && hi <= b) {
            return t[x];
        }

        int mi = (lo + hi) >> 1;
        return min(get(a, b, x * 2, lo, mi),
                   get(a, b, x * 2 + 1, mi, hi));
    }
} special, updates, tracker;

void moveSpecial(int a, int b) {
    special.upd(a, a+1, +inf);
    special.upd(b, b+1, -inf);
}
void addSpecial(int a) {
    special.upd(a, a+1, -inf);
}

long long sum;

void solve(int x, int d, int type) {
    int cnt = 0;
    while(a[x] > 0) {

        // check if this is valid with previous chairs
        if (tracker.get(x, off) < 2 * d) {
            break;
        }

        // check if this chair can be taken
        if (x - updates.get(x, x + 1) < type * d * 2) {
            break;
        }

        // if this is segment with right storage
        if (r[x] != -1) {
            int spec = specialChair[r[x]];
            if (type) spec = min(spec, x);

            if (a[spec] == 1 && spec == x) {
                if (!type) break;
                spec = before[spec];
            }

            if (spec <= l[x]) break;
            if (a[spec] <= 0) break;

            moveSpecial(specialChair[r[x]], spec);
            special.upd(x + type, off, -2 * d);

            int diff = special.get(0, off);

            if (diff < 0) {
                special.upd(x + type, off, 2 * d);
                moveSpecial(spec, specialChair[r[x]]);
                break;
            }
            specialChair[r[x]] = spec;
        }

        if (cnt == 0) {
            tracker.upd(x, x + 1, - inf - 2 * d * (type - 1));
        }

        tracker.upd(x, off, -2 * d);
        updates.upd(x, off, 2 * d);

        a[x] --;
        sum --;
        cnt ++;
    }
}

int main() {
    int n; cin >> n;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] != -1) sum += a[i];
    }

    int tmp = -1;
    for (int i = 0; i < n; ++i) {
        if (a[i] == -1) {
            tmp = i;
        }
        l[i] = tmp;
    }
    tmp = -1;
    for (int i = n - 1; i >= 0; --i) {
        if (a[i] == -1) {
            tmp = i;
        }
        r[i] = tmp;
    }

    tmp = -1;
    for (int i = 0; i < n; ++i) {
        before[i] = tmp;
        if (a[i] > 0) {
            tmp = i;
        }
    }

    special.init();
    tracker.init();

    // setup sepcial chair moves (left on first pass)
    for (int i = 0; i < n; ++i) {
        if (a[i] > 0 && r[i] != -1 && before[r[i]] == i) {
            addSpecial(i);
            specialChair[r[i]] = i;
        }
    }

    vector<pair<int, pii>> candidates;
    for (int i = 0; i < n; ++i) {
        if (a[i] > 0) {
            if (r[i] != -1) {
                candidates.push_back({r[i] - i, {i, 1}});
            }
            if (l[i] != -1) {
                candidates.push_back({i - l[i], {i, 0}});
            }
        }
    }
    sort(candidates.begin(), candidates.end());

    for (auto candidate : candidates) {
        int x = candidate.second.first;
        int d = candidate.first;
        int type = candidate.second.second;

        solve(x, d, type);
    }

    for (int i = 0; i < n; ++i) {
        if (a[i] > 0 && r[i] != -1) {
            a[r[i]] = -2;
        }
        if (a[i] == -2) sum --;
    }

    cout << sum << endl;
}

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