Submission #1146947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146947		blackslex	Sails (IOI07_sails)	C++20	5 / 100	986 ms	5360 KiB

sails

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int N = 1e5 + 5;
int n, lz[N * 4];

struct node {
    int val, mx;
    node() : val(0), mx(0) {}
    node(int val) : val(val), mx(val) {}
    friend node operator + (const node &l, const node &r) {
        node res = node();
        res.val = l.val + r.val;
        res.mx = max(l.mx, r.mx);
        return res;
    }
} segm[N * 4];

void push (int l, int r, int idx) {
    segm[idx].val += (r - l + 1) * lz[idx];
    segm[idx].mx += lz[idx];
    if (l < r) {
        lz[idx * 2 + 1] += lz[idx];
        lz[idx * 2 + 2] += lz[idx];
    }
    lz[idx] = 0;
}

void upd (int l, int r, int idx, int tl, int tr, int val) {
    push(l, r, idx);
    if (l > tr || r < tl) return;
    if (l >= tl && r <= tr) {
        lz[idx] += val;
        push(l, r, idx);
        return;
    }
    int mid = (l + r) >> 1;
    upd(l, mid, idx * 2 + 1, tl, tr, val);
    upd(mid + 1, r, idx * 2 + 2, tl, tr, val);
    segm[idx] = segm[idx * 2 + 1] + segm[idx * 2 + 2];
}

node qr (int l, int r, int idx, int tl, int tr) {
    push(l, r, idx);
    if (l > tr || r < tl) return node();
    if (l >= tl && r <= tr) return segm[idx];
    int mid = (l + r) >> 1;
    return qr(l, mid, idx * 2 + 1, tl, tr) + qr(mid + 1, r, idx * 2 + 2, tl, tr);
}

int main() {
    scanf("%d", &n);
    vector<pii> c(n);
    for (auto &[x, y]: c) scanf("%d %d", &x, &y);
    reverse(c.begin(), c.end());
    int k = 1e5;
    for (auto &[x, y]: c) {
        int cmn = 1, cmx = x;
        int z0 = qr(1, k, 0, 1, 1).val, zn = qr(1, k, 0, x, x).val;
        if (z0 < zn) {
            {
                int l = cmn, r = cmx;
                while (l < r) {
                    int mid = (l + r + 1) >> 1;
                    if (qr(1, k, 0, cmn, mid).mx == z0) l = mid;
                    else r = mid - 1;
                }
                int z = min(y, l);
                upd(1, k, 0, cmn, cmn + z - 1, 1);
                y -= z;
                cmn += z;
            }
        } else {
            {
                int l = cmn, r = cmx;
                while (l < r) {
                    int mid = (l + r) >> 1;
                    if (qr(1, k, 0, mid, cmx).mx == zn) r = mid;
                    else l = mid + 1;
                }
                int z = min(y, cmx - l + 1);
                upd(1, k, 0, cmx - z + 1, cmx, 1);
                y -= z;
                cmx -= z;
            }
            {
                int l = cmn, r = cmx;
                while (l < r) {
                    int mid = (l + r + 1) >> 1;
                    if (qr(1, k, 0, cmn, mid).mx == z0) l = mid;
                    else r = mid - 1;
                }
                int z = min(y, l);
                upd(1, k, 0, cmn, cmn + z - 1, 1);
                y -= z;
                cmn += z;
            }
        }
        upd(1, k, 0, cmx - y + 1, cmx, 1);
    }
    ll ans = 0;
    for (int i = 1; i <= 10; i++) {
        int z = qr(1, k, 0, i, i).val;
        ans += z * (z - 1) / 2;
    }
    printf("%lld", ans);
}

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
sails.cpp:57:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     for (auto &[x, y]: c) scanf("%d %d", &x, &y);
      |                           ~~~~~^~~~~~~~~~~~~~~~~

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