Submission #753107

#	Time	Username	Problem	Language	Result	Execution time	Memory
753107		Nhoksocqt1	Sails (IOI07_sails)	C++17	100 / 100	77 ms	47880 KiB

sails

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

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
#define sz(x) int((x).size())
typedef long long ll;
typedef pair<int, int> ii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;

struct Line {
    ll a, b;

    Line(ll _a = 0, ll _b = 1e18) : a(_a), b(_b) {};

    ll inline get(ll x) const {
        return a * x + b;
    }

    bool operator != (const Line &line) const {
        return (a != line.a || b != line.b);
    }

} tr[4 * MAXN];

struct History {
    int pos, id;
    Line lines;
};

vector<History> history;
ll sum[MAXN], sumc[MAXN], P[MAXN][17];
int sumn[MAXN], numn[MAXN], numc[MAXN];
int height[MAXN], maxHeight, nArr;

void update(int id, int l, int r, Line lines, int cnt) {
    Line low(tr[id]), high(lines);
    int mid = (l + r) >> 1;

    if(low.get(l) > high.get(l))
        swap(low, high);

    if(low.get(r) <= high.get(r)) {
        if(tr[id] != low)
            history.push_back({cnt, id, tr[id]});

        tr[id] = low;
        return;
    }

    if(low.get(mid) <= high.get(mid)) {
        if(tr[id] != low)
            history.push_back({cnt, id, tr[id]});

        tr[id] = low;
        update(id << 1 | 1, mid + 1, r, high, cnt);
    } else {
        if(tr[id] != high)
            history.push_back({cnt, id, tr[id]});

        tr[id] = high;
        update(id << 1, l, mid, low, cnt);
    }
}

ll queryMin(int pos) {
    ll res = tr[1].get(pos);
    int id(1), l(1), r(nArr);
    while(l != r) {
        if(tr[id].a == 0 && tr[id].b >= 1e18)
            break;

        int mid = (l + r) >> 1;
        if(pos <= mid) {
            id = id << 1;
            r = mid;
        } else {
            id = id << 1 | 1;
            l = mid + 1;
        }

        res = min(res, tr[id].get(pos));
    }

    return res;
}

void rollback(int x) {
    while(sz(history) && history.back().pos == x) {
        tr[history.back().id] = history.back().lines;
        history.pop_back();
    }
}

inline ll getMin(int l, int r) {
    int log = 31 - __builtin_clz(r - l + 1);
    return min(P[l][log], P[r - (1 << log) + 1][log]);
}

bool check2(int h, int maxc, ll sumu) {
    int nNow = nArr - sumn[h - 1];
    for (int i = h; i <= maxHeight; ++i) {
        sumu += min(maxc, nNow) - sumc[i];
        nNow -= numn[i];
        //cout << h << ' ' << maxc << ' '<< i << ' ' << sumu << '\n';
        if(sumu < 0)
            return false;
    }

    return true;
}

bool check(int h, int maxc, ll sumu) {
    if(queryMin(maxc) - 1LL * maxc * (h - 1) + sum[h - 1] + sumu < 0)
        return false;

    int nNow = nArr - sumn[h - 1];
    int l(h), r(maxHeight - 1), opt(h);
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(nNow - sumn[mid] + sumn[h - 1] >= maxc) {
            opt = mid + 1;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }

    sumu += 1LL * maxc * (opt - h + 1) - sum[opt] + sum[h - 1];
    if(sumu < 0 || opt < maxHeight && getMin(opt + 1, maxHeight) - P[opt][0] + sumu < 0)
        return false;

    return true;
}

void process(void) {
    cin >> nArr;

    ll sumcasd(0);
    for (int i = 1; i <= nArr; ++i) {
        cin >> height[i] >> numc[i];
        sumcasd += numc[i];
        //height[i] = Random(1, 100000); numc[i] = Random(1, height[i]); cout << height[i] << ' ' << numc[i] << '\n';
        maxHeight = max(maxHeight, height[i]);
        ++sumc[height[i] - numc[i] + 1], --sumc[height[i] + 1];
        ++numn[height[i]];
    }

    int nNow(nArr);
    for (int i = 1; i <= maxHeight; ++i) {
        sumc[i] += sumc[i - 1];
        sumn[i] = sumn[i - 1] + numn[i];
        sum[i] = sum[i - 1] + sumc[i];
        P[i][0] = P[i - 1][0] + nNow - sumc[i];
        nNow -= numn[i];
    }

    for (int j = 1; (1 << j) <= maxHeight; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= maxHeight; ++i) {
            P[i][j] = min(P[i][j - 1], P[i + (1 << (j - 1))][j - 1]);
        }
    }

    for (int i = maxHeight; i > 0; --i)
        update(1, 1, nArr, Line(i, -sum[i]), i);

    ll res(0), sum(0);
    int maxr(nArr); nNow = nArr;
    for (int i = 1; i <= maxHeight; ++i) {
        maxr = min(maxr, nNow);
        while(maxr > 1 && check(i, maxr - 1, sum))
            --maxr;

        res += 1LL * maxr * (maxr - 1) / 2;
        sum += maxr - sumc[i];
        nNow -= numn[i];
        rollback(i);
    }

    cout << res << '\n';
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    process();
    return 0;
}

Compilation message (stderr)

sails.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
sails.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
sails.cpp: In function 'bool check(int, int, ll)':
sails.cpp:140:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  140 |     if(sumu < 0 || opt < maxHeight && getMin(opt + 1, maxHeight) - P[opt][0] + sumu < 0)
      |                    ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10